Parity using "modulo"

Question

I ran into this, while looking up algorithms that find parity, which is supposedly efficient:

function usingModulo(v) {
    v ^= v >> 1
    v ^= v >> 2
    v = (v & 0x11111111) * 0x11111111
    return (v >> 28) & 1
}

Could some one please explain how this actually works?

Answer 1

v ^= v >> 1

After this, bit 2i in v is the parity of bits 2i and 2i+1.

v ^= v >> 2

After this, bit 4i in v is the parity of bits 4i,4i+1,4i+2,4i+3.

v = (v & 0x11111111) * 0x11111111

After this, the top 4 bits of the v contain the sum of the bits at position 4i in the old v, and in particular the bit at position 28 will contain the least significant bit of the sum, which will be the parity of all the bits in the input number.

return (v >> 28) & 1

This extracts the bit at position 28 (the parity of all bits).

UPDATE

To explain more about the multiplication in step 3 it may help to think of the multiplication as a series of shifts and adds.

For example, to multiply a number x by 111 in base 10, you can add up 100x and 10x and x.

Similarly, multiplying x by 0x11111111 is the same as shifting x by 0,4,8,... and adding the results.

When thinking as a series of shifts and adds, it may make more sense that the top bits will contain all the parities shifted and added together.