Find if a number is divisible by 17 using bitwise operatorsResult 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)); } ![]() This is because all of them can be broken up using 2k |
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: