CODEWITHSUNDEEP
mathbit-manipulation
Peter Lapisu
Peter Lapisu

Reputation: 21005

Why does this modulo bit operation work?

i found out, that you can do modulo using this :

x % m == (x + x / m) & m

but i cannot understand why its working...

like for 8 % 7 == (8 + 8 / 7) & 7, this is

x = 8 =          0001 0000
x / 7 = 1 =      1000 0000
x + x / 7 = 9 =  1001 0000
9 & 7 =          1001 0000 & 1110 0000 = 1000 0000 = 1

Upvotes: 3

Views: 160

Answers (1)

Beta
Beta

Reputation: 99144

N = 7k + m, m<7
N/7 = k
N + N/7 = 8k + m
(N + N/7) & 7 = (8k + m) & 7
              = m & 7
              = m

It works for any 2n-1 number, not just 7.

Upvotes: 4

Related Questions