Result: x % n = x & (n-1), where n is some power of 2 i.e. n = 1 << i.
Why this works?
Lets take an example of 14 % 4,
14 = 1110 = 8(4th-Bit) + 4(3rd-Bit) + 2(2nd-Bit) + 1(1st-Bit)
14 = 8 + 4 + 2 + 0
14 = (4*2) + (4) + 2 + 0
This implies 14 % 4 = (4*3 + 2) % 4 = 2 % 4 = 2 i.e. only the last two bits of 14 contribute to the remainder when dividing by 4. In general, when dividing by 1 << i, only the last i bits of x determine the remainder. This remainder can be computed efficiently with x & (n - 1).
Uses
Though a simple observation, but can be leveraged to solve some interesting variations of problem, try Make Almost Equal With Mod.
Have you used this technique within more complex data structures, like circular buffers or ring arrays? I’m curious if the trick applies well to these types of use cases.
Not yet, but I would like to try. Do you have any problem on those topics?
this is also useful in solving 2036F - XORificator 3000