[Solved] How to know number is divisible by 3 or any odd number using bitwise operator in python [closed]

by


We know school principle: if the sum of decimal digits is divisible by 9, then number is divisible by 9.
The same approach works for any base of number system b and divisor b-1: for base=4 we can check that sum of two-bits chunks is divisible by 3. We can repeat this process until all but two bits become zero.

11dec = 1011bin: 
10 + 11 = 101
01 + 01 = 10 - not divisible

21dec = 10101bin: 
01 + 01 + 01 = 11 - divisible


def divis3(x):
    while(x & (~3)):   # added more bitwiseness :) instead of (x > 3)
        sum = 0
        while (x):
            sum += x & 3  # extract two least significant bits
            x >>= 2       # shift value to get access to the next pair of bits
        x = sum
    return (x == 0 or x==3)

solved How to know number is divisible by 3 or any odd number using bitwise operator in python [closed]