Make delicious recipes!

Find if a number is divisible by 17 using bitwise operators


Result of division is a quotient and a remainder.
n/17 = floor(n/17) + (n%17)/17 (Assuming we are storing result in a float, not int)

Multiplying numerator and denominator on the right-hand-size by 16:

n/17 = 16n / 17*16
     = (17-1)n / 17*16
     = n/16 - n/17*16

Now, replacing n/16 with first definition: n/16 = floor(n/16) + (n%16)/16, we get:
     = floor(n/16) + (n%16)/16    -  (floor(n/16) + (n%16)/16)/17
     = floor(n/16)                -  (floor(n/16) - 17*(n%16)/16 + (n%16)/16)/17
     = floor(n/16)                -  (floor(n/16) - n%16)/17

The left-hand-side of this equation is n/17. That will be an integer only when the right-hand-side is an integer.
floor(n/16) has to be an integer by definition.
So the whole left-hand-side would be an integer if (floor(n/16) - n%16)/17 is also an integer.

This implies n is divisible by 17 if (floor(n/16) - n%16) is divisible by 17


Recursively, this can be written as:
boolean isDivBy17(int n)
{
    if (n == 0 || n == 17)
        return true;
    if (n < 17)
        return false;
 
    return isDivBy17((int)(n>>4) - (int)(n&15));
}


Note that this property holds true for any n of the form 2k + 1 like 5, 9, 17, 33 and so on
This is because all of them can be broken up using 2k





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal