can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'.

I want the efficient solution to this problem ..

can someone help ??

This is a discussion on *divisibility by 3* within the **C Programming** forums, part of the General Programming Boards category; can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'.
I want the ...

- 06-29-2007 #1

- Join Date
- Sep 2006
- Posts
- 19

## divisibility by 3

can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'.

I want the efficient solution to this problem ..

can someone help ??

- 06-29-2007 #2
Yes (recursively add the digits in base 10 and check for divisibility when only one digit is left), but it will probably less efficient than using modulo at machine level.

Originally Posted by**Bjarne Stroustrup (2000-10-14)**

- 06-29-2007 #3

- Join Date
- Sep 2006
- Posts
- 19

yes right .. but still i have to check the divisibility when one digit is left .. as you said ...

so the question is still same how to divide the number or check divisibility of a number by 3 [:-)]

- 06-29-2007 #4
You can't figure that one out by yourself? Look at all of the single digit numbers that are divisible by 3, starting with 0. There you go. Hardcode those digits in as what are required.

- 06-29-2007 #5yes right .. but still i have to check the divisibility when one digit is left .. as you said ...

Though if you actually have to implement this, then most likely you would read the number as a string. If so, it makes more sense to add the first digit to the second, determine its remainder after division by three (perhaps by means of a switch with 19 cases), and add that remainder to the third digit, determine the new remainder, and so on until the entire numeric string is processed.Originally Posted by**Bjarne Stroustrup (2000-10-14)**

- 06-29-2007 #6
Well, do "old skool" division

Using iterated subtraction (ie num -= divisor).

if the remainder is 0, then the num is divisible by 3, otherwise it's not.

- 06-29-2007 #7Well, do "old skool" division

Using iterated subtraction (ie num -= divisor).

if the remainder is 0, then the num is divisible by 3, otherwise it's not.Originally Posted by**Bjarne Stroustrup (2000-10-14)**

- 06-29-2007 #8
Sorry, didn't see they were asking for an efficient solution

- 06-29-2007 #9

- Join Date
- Sep 2006
- Posts
- 835

I suspect that converting the number to a string involves extracting decimal digits by internally using / and % by 10 repeatedly (although hidden) so would probably be less efficient than a single explicit % by 3. On the other hand, the rule for testing a decimal number for divisibility by 3 relies on the fact that 10 is congruent to 1 mod 3, so for example the remainder of 6738430 mod 3 is the same as that of 673843 mod 3, and the rule follows by induction. In the same way, one can get a similar rule for testing a binary number for divisibility by 3 by noting that 4 is congruent to 1 mod 3, so 10001110010100 (base 2) has the same remainder mod 3 as 100011100101 (base 2). You just lop off the last 2 zeroes. This means that the remainder of 10110101001010 mod 3 is the same as that of 10 + 11 + 01 + 01 + 00 + 10 + 10. If the number is stored in an unsigned integral type, then one can repeatedly use "& 3" to read off the two rightmost binary digits, add to a running total, then ">>= 2" to right shift by 2. I doubt whether this would be more efficient unless it was implemented in hardware, though.

Edit: Of course, there are tricks to speed it up - for example, the running total can be reduced immediately whenever it gets >= 100 (base 2), and each instance of 00 or 11 can be ignored, since they're both divisible by 3.

Edit: Since 16 is congruent to 1 mod 3, the rule for testing for divisibility by 3 by testing the sum of the digits works for base 16 (hexadecimal) as well as base 10.

Edit: Here you go:

Code:unsigned int remainderby3(unsigned int i) { /* good for 32-bit unsigned int */ i = (i & 65535) + (i >> 16); i = (i & 65535) + (i >> 16); i = (i & 255) + (i >> 8); i = (i & 255) + (i >> 8); i = (i & 15) + (i >> 4); i = (i & 15) + (i >> 4); i = (i & 3) + (i >> 2); i = (i & 3) + (i >> 2); return (i != 3)? i : 0; }

Last edited by robatino; 06-29-2007 at 09:22 AM.

- 06-29-2007 #10
I was quite skeptical of the function robatino posted, however I wrote a test program and I can tell you that it works for every number from 0 to 0x7FFFFFFF!

I didn't do any speed tests though. It may be faster in some circumstances, but it increases the code size, so there will probably be cases where it is slower due to the code for some inner loop no longer fitting in the instruction cache any more.

When you know already that the number is small, then some of the steps can obviously be removed, so I can definitely see cases where this will certainly be faster.My homepage

Advice: Take only as directed - If symptoms persist, please see your debugger

Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

- 06-29-2007 #11I suspect that converting the number to a string involves extracting decimal digits by internally using / and % by 10 repeatedly (although hidden) so would probably be less efficient than a single explicit % by 3.

I am not so sure how concerned we should really be for fine tuning the performance beyond the general algorithm: this sounded like a homework question to me from the start.Originally Posted by**Bjarne Stroustrup (2000-10-14)**

- 06-29-2007 #12

- Join Date
- Jul 2005
- Posts
- 14

- 06-29-2007 #13How else would you convert it?Originally Posted by
**Bjarne Stroustrup (2000-10-14)**

- 06-29-2007 #14

- Join Date
- Sep 2006
- Posts
- 835

This was just a quick-and-dirty implementation. The idea is that 2^n is congruent to 1 mod 3 when n is any even positive integer, so the add-the-digits test for divisibility by 3 works in base 4, 16, 64, 256, etc. So I do it first in base 65536 == 2^16, where a 32-bit unsigned int can be represented with 2 digits. I add the two digits, then repeat to take care of the carry and ensure that the result is just one digit. Then repeat with base 256 == 2^8 to reduce to a single base 256 digit, etc. Once down to a single base 4 digit, it's either 0, 1, 2, or 3, and I just replace 3 by 0. There's probably a way to avoid having two copies of each line. I'm guessing that this is slower than a simple %3 but haven't done speed tests. It could easily be faster if done in hardware.

- 06-29-2007 #15
I don't think he's starting with chars which is where you two lost each other, I think he is starting from an integer and not necessarily an input from the command line. So what he need is a general purpose function that takes an int and returns if it's divisible by 3 and therefore was stating it would be difficult to parse the individual digits without using / or %, but you could always convert the int to a string first with itoa or stringstreams

Last edited by Darryl; 06-29-2007 at 03:50 PM.

- Exactly how to get started with C++ (or C) today
- C Tutorial
- C++ Tutorial
- 5 ways you can learn to program faster
- The 5 Most Common Problems New Programmers Face
- How to set up a compiler
- 8 Common programming Mistakes
- What is C++11?
- Creating a game, from start to finish

- How to create a shared library on Linux with GCC - December 30, 2011
- Enum classes and nullptr in C++11 - November 27, 2011
- Learn about The Hash Table - November 20, 2011
- Rvalue References and Move Semantics in C++11 - November 13, 2011
- C and C++ for Java Programmers - November 5, 2011
- A Gentle Introduction to C++ IO Streams - October 10, 2011