Modulo using Bitwise Operators

I was asked a question today how can we check whether a number N is divisible by 7 using bitwise operators. Then I was asked to do the same for 3.

Initial Approach (wrong approach):

To observe bit patterns

for e.g. 3 = 00000011, 6 = 00000110, 9 = 00001001 and so on...

I thought that all the binary 1's will conform to either 11 or 1001. BUT this was wrong, it failed for 81.

The Final Approach (courtesy google):

After a bit of googling I found an approach which has to do with modulo arithmetic in Numbers Theory.

(3)10 = (11)2 Note: I will use this notation whenever needed to avoid confusion

The algorithm:

1 - Take the Binary of the number

2 - Divide the entire sequence of bits into pairs of bits

3 - Take the sum of all these pairs

4 - If the sum is greater than three then repeat Steps 1, 2, 3 for this sum

5 - If sum is 0 or 3 then number is divisible by three else not. Moreover this sum will have the remainder.

For e.g. let us take (assume 8 bits for simplicity)

First Iteration:
(40)10 = (00101000)2 = 00 10 10 00 ==> Sum = (4)10
(41)10 = (00101001)2 = 00 10 10 01 ==> Sum = (5)10
(42)10 = (00101010)2 = 00 10 10 10 ==> Sum = (6)10

Second Iteration:
(4)10 = (00000100)2 = 00 00 01 00 ==> Sum = (1)10 ==> 40%3 = 1
(5)10 = (00000101)2 = 00 00 01 01 ==> Sum = (2)10 ==> 41%3 = 2
(6)10 = (00000110)2 = 00 00 01 10 ==> Sum = (3)10 ==> 42%3 = 0

Thus 42 is divisible

Similar approach is for checking divisibility with 7. Only this time instead this time taking pairs of consecutive bits we take triplets because (7)10 = (111)2

Consider a sample code for N % 7 using the above approach.

unsigned int calcRemainder(unsigned int n)
{
unsigned int sum = 0;
while(1)
{
  sum = 0;      // Correction done as mentioned by Jitendra
  while(n)
  {
    sum += n&7;
    n = n >> 3; // seven is 3 1s (ones) so shift by three
  }
  if(sum>7)
    n = sum;
  else if(sum==7)
    return 0;
  else
    return sum;
}
}

The code looks similar to what we do for checking divisibility with 3 or 9 in decimal number system. We take the sum of all the digits recursively till we get a single either divisible or not divisible by 3 or 9.

The only limitation that I could observe was that this technique works for numbers like which of the form 2^n - 1 such as 3, 7, 15. (I havent tried it for other numbers anyways :P )

The link I referred to is

http://stackoverflow.com/questions/48053/is-there-an-alternative-to-using-modulus-in-c-c

However I wasn't able to deduce this mathematically (I'm not a maths guy). So If any of you Mathos can give me mathematical proof and may be extend this algorithm for other numbers as well, kindly add them as a comment, or mail mel. I will surely update the blog.