mod & div operations when denominator is power of 2

mod and div operations are expensive and so when the denominator is a power of 2, we can use bitwise operators for performance.

Tricks:

1. If a number den is a power of 2 then den&den-1 is 0.
2. When the denominator is power of 2, denominator-1 has x number of 1s as lsb where 2x = den.
3. The lsb digits are the mod result and the msb digits are the div result.

mod result = 3
1011 //n = 11, den = 4
div result = 2

int mod(n, den):
    if isPowerOf2(den-1):
        return n & (den-1)
    else
        return n % den

int div(n, den):
    if isPowerOf2(den-1):
        return n & (~(den-1)) >> countOf1Bits(den-1)
    else
        return n / den
        
int countOf1Bits(n)
    count = 0
    while n > 0:
        n &= n-1
        count++
    return count

bool isPowerOf2(den):
    return den > 0 && (den & (den-1)) == 0

example:

n = 11
den = 4

mod(11, 4):
1011 //11
0100 // 4
0011 // 4-1
0011 //11 & (4-1) = 3 = 11 % 4

div(11, 4):
1011 //11
0100 // 4
0011 // 4-1
1100 // ~(4-1)
1000 //11 & (~(4-1))
0011 // countOf1Bits(4-1) = 2
0010 //11 & (~(4-1)) >> countOf1Bits(4-1) = 2 = 11 / 4

[Hat tip to CTCI]