Since bitwise operations are relatively efficient, in some cases, when b is 2 to the power of n, the following substitution holds:
a % b = a & (b-1)
notes:
- b must be a power of 2
This guarantees that b has only its highest bit set to 1 and all other bits 0; after subtracting 1, the high 1 bit is cleared and all lower bits become 1.
After subtracting one, the highest bit is 0 and all the following bits are 1 (b-1 is the largest possible remainder), so this is equivalent to ANDing the low bits with the original number
For example, 14%8: taking the remainder is equivalent to extracting the low bits, and the largest possible remainder is 7. 14 in binary is 1110, 8 is 1000, and 8-1 = 7 is 0111. Since the low bits are now all 1, ANDing with 14 extracts exactly the remainder held in its low bits