Verify divisibility rules using bitwise operations

Question

How can I verify if a number n is divisible by x using bitwise operations?

I find lot of related links on this but I don't clearly understand them as they were not in Python. For example, what if I want to verify if 81 is divisible by 3, 9 or 4?

I want to use bitwise operations and I want to understand how to implement this using Python.

Answer 1

Bitwise operation as their name let guess operate on binary representation of numbers. That means that they will be highly efficient to test divisibility by a power or 2, but hardly usable for any other case.

Examples:

• n divisible by 2 : n & 1 == 0
• n divisible by 4 : n & 3 == 0
• n divisible by 8 : n & 7 == 0

There are other divisibility rules that could be used: you could adapt the casting out 9 or 11 to test divisibility by 15 or 17 (base 16 uses to nibbles per byte), but as one single integer division is often faster than making many simpler operations (accumulator directly processes numbers of 32 or 64 bits) they are seldom used...

If your requirement is to test divisibility by 3 and 9, you could adapt casting out 9 for 3 = 4 - 1, and 11 for 9 =8+1. 81 = 0b1010001

• 3: sum of 2 bit digits must be divisible by 3 - starting with little weights : 01+00+01+01=0b11 (=3): divisible
• 9: sum of odd 3 bit digits minus sum of even ones must be divisible by 9=0b1001 - odd: 001+001=010, even: 010 - difference is 0: divisible

You can code this easily with shifts (>>) and binary &