[superprismatic]

Suppose you want to determine the parity

of the number of ones in the binary

representation of a 32-bit integer.

Given that all integer arithmetic,

logical, and shift (circular or end

around) operations each count as one

operation, what is the fewest number of

operations needed to determine the

parity of the number of ones in a 32-bit

integer?

[Guest]

Is that the African or European swallow?

[Guest]

I would say 31. just perform an xor operation on all the bits and if the result is 0 then the parity is even. If the result is 1, the parity is odd.

[EventHorizon]

Shift left by 16 bit and xor with the original.

Shift left 8 and xor with the one before this shift.

Shift left 4 and xor with the one before this shift.

Shift left 2 and xor with the one before this shift.

Shift left 1 and xor with the one before this shift.

This is essentially a binary search kind of way to xor all the bits.

This is 10 operations and the most significant (one all the way left) is the parity. I'll think about it more...

[EventHorizon]

Source

unsigned int v; // word value to compute the parity of

v ^= v >> 16;

v ^= v >> 8;

v ^= v >> 4;

v &= 0xf;

return (0x6996 >> v) & 1;

As written it is 9 operations... if you can just say that the bit is in the lowest position, then it takes 8 and you don't need to mask out the least significant bit. If you can be sure the shift will shift in 0's (eg, if that shift operation is available, which I think is the case for unsigned ints in c++), you can shave the masking of the least significant 4 bits and that leaves 8 or 7 operations based on the previous question of the need for the final mask.

For those of you who cannot understand the code, here's an explanation:

The first three lines are bit shifting and XORing like my solution.

The fourth line masks out the least significant 4 bits (seems unnecessary unless the int was signed).

These last four bits can have values from 0 to 15, so instead of taking 4 more operations this code uses a mini lookup table (the 0x6996), and masks out the answer (the & 1).

The lookup table in binary is 0110 1001 1001 0110.

So if the value after masking the least significant 4 bits was 0, there is no shift and the LSB is 0 in the lookup table.

If the value is 1, the table is shifted 1 to be 0011010011001011, and the LSB is 1. Etc.

So it seems my previous answer had the essential parts (save the lookup table optimization). Shifting right instead would have ended up with 1 or 0 after all is done (instead of 0 and 2^31).

If you have to do this a lot or just very quickly after an initial load time, you could always build a bigger lookup table and only do enough shifting to decrease the size of the lookup table to the amount of memory you can devote to it.

Well, that's probably more than you wanted so I'll stop here.

Yay! 400th post

Edited May 29, 2011 by EventHorizon

[superprismatic]

Source

unsigned int v; // word value to compute the parity of

v ^= v >> 16;

v ^= v >> 8;

v ^= v >> 4;

v &= 0xf;

return (0x6996 >> v) & 1;

As written it is 9 operations... if you can just say that the bit is in the lowest position, then it takes 8 and you don't need to mask out the least significant bit. If you can be sure the shift will shift in 0's (eg, if that shift operation is available, which I think is the case for unsigned ints in c++), you can shave the masking of the least significant 4 bits and that leaves 8 or 7 operations based on the previous question of the need for the final mask.

For those of you who cannot understand the code, here's an explanation:

The first three lines are bit shifting and XORing like my solution.

The fourth line masks out the least significant 4 bits (seems unnecessary unless the int was signed).

These last four bits can have values from 0 to 15, so instead of taking 4 more operations this code uses a mini lookup table (the 0x6996), and masks out the answer (the & 1).

The lookup table in binary is 0110 1001 1001 0110.

So if the value after masking the least significant 4 bits was 0, there is no shift and the LSB is 0 in the lookup table.

If the value is 1, the table is shifted 1 to be 0011010011001011, and the LSB is 1. Etc.

So it seems my previous answer had the essential parts (save the lookup table optimization). Shifting right instead would have ended up with 1 or 0 after all is done (instead of 0 and 2^31).

If you have to do this a lot or just very quickly after an initial load time, you could always build a bigger lookup table and only do enough shifting to decrease the size of the lookup table to the amount of memory you can devote to it.

Well, that's probably more than you wanted so I'll stop here.

Yay! 400th post

Nice! The last part of making that lookup table was a real stroke of insight!

I have a routine which keeps shifting and XORing until the parity is in the

low order bit, then I mask it off. So, I was expecting the lowest to be 11

operations. The lookup table allows it in 9 as you showed. I'm amazed at

the ingenuity shown on this site.

I have two comments about your explanation:

(1) I suppose that v ^= v >>16 means to XOR v with v after right shifting by 16.

This (and the others like it) doesn't anihilate high order bits even if 0's are

shifted in. So, the last 4 bits always needs to be masked before shifting

0x6996. Also, I meant to get to a single bit, so the final masking with 1 is

necessary.

(2) I think a bigger lookup table would be way more expensive than the shifting

and XORing. The reason your way is so good is that it accomplishes a lookup

using a shift of a constant.

[Guest]

Source

unsigned int v; // word value to compute the parity of

v ^= v >> 16;

v ^= v >> 8;

v ^= v >> 4;

v &= 0xf;

return (0x6996 >> v) & 1;

As written it is 9 operations... if you can just say that the bit is in the lowest position, then it takes 8 and you don't need to mask out the least significant bit. If you can be sure the shift will shift in 0's (eg, if that shift operation is available, which I think is the case for unsigned ints in c++), you can shave the masking of the least significant 4 bits and that leaves 8 or 7 operations based on the previous question of the need for the final mask.

For those of you who cannot understand the code, here's an explanation:

The first three lines are bit shifting and XORing like my solution.

The fourth line masks out the least significant 4 bits (seems unnecessary unless the int was signed).

These last four bits can have values from 0 to 15, so instead of taking 4 more operations this code uses a mini lookup table (the 0x6996), and masks out the answer (the & 1).

The lookup table in binary is 0110 1001 1001 0110.

So if the value after masking the least significant 4 bits was 0, there is no shift and the LSB is 0 in the lookup table.

If the value is 1, the table is shifted 1 to be 0011010011001011, and the LSB is 1. Etc.

So it seems my previous answer had the essential parts (save the lookup table optimization). Shifting right instead would have ended up with 1 or 0 after all is done (instead of 0 and 2^31).

If you have to do this a lot or just very quickly after an initial load time, you could always build a bigger lookup table and only do enough shifting to decrease the size of the lookup table to the amount of memory you can devote to it.

Well, that's probably more than you wanted so I'll stop here.

Yay! 400th post

From the source you linked to, one can reduce the operations from 9 (compute parity in parallel) to 8 (compute parity with a multiply).

unsigned int v; // 32-bit word

v ^= v >> 1;

v ^= v >> 2;

v = (v & 0x11111111U) * 0x11111111U;

return (v >> 28) & 1;

As I do not program in C or C++ I can not say this is the minimum number of operations. I do believe there are some programming languages that can reduce the number of operations given, yet I gather the solution sought is with C or C++.