Bug in popcount implementation in Bitvec.cpp

[bpanda-dev]

Hi,

The 32-bit popcount implementation in Bitvec.cpp has misplaced parentheses, the 0xF0F0F0F mask is applied before the addition instead of after. This breaks correctness.

uint32_t popcount ( uint32_t v )
{
	v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
	uint32_t c = ((v + ((v >> 4) & 0xF0F0F0F)) * 0x1010101) >> 24; // count <----- MASK APPLIED BEFORE ADDITION

	return c;
}

Correct implementation:

Correct Logic requires the mask 0xF0F0F0F to be applied after the addition. [1]

uint32_t popcount ( uint32_t v )
{
	v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
	uint32_t c = (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; // count <----- MASK APPLIED AFTER ADDITION

	return c;
}

[1]. Bit Twiddling Hacks

cheers,
Bikram

[rurban]

Oh my god, thanks a lot!

[tansy]

What tests depend on it?