CODEWITHSUNDEEP
algorithmbit-manipulation
Want_to_be_unknown
Want_to_be_unknown

Reputation: 53

Set bit counting

Hi I am trying to analyze a function

int countBit(uint32_t n) {
    n = (n & 0x55555555) + ((n & 0xAAAAAAAA) >> 1);
    n = (n & 0xC30C30C3) + ((n & 0x0C30C30C) >> 2) + ((n & 0x30C30C30) >> 4);
    return n % 63;
}

Now I've already figured out that it counts the number of set bits (originally the function name has been different so it was not obvious.)

I also know that the line

n = (n & 0x55555555) + ((n & 0xAAAAAAAA) >> 1);

gives the number of 1 in subsequent pairs. However after that I am at lost. Individually I know what the code is doing, but I do not know why it does that and what is the idea behind it.

Upvotes: 1

Views: 133

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59323

Oh, I haven't seen this one before. It's pretty clever, although I wonder how fast the modulus is compared to more bit twiddling.

Anyway, after n = (n & 0x55555555) + ((n & 0xAAAAAAAA) >> 1), we have 16 2-bit counts.

(n & 0xC30C30C3) isolates the 6 counts that are shifted by multiples of 6 bits, i.e., multiplied by multiples of 64. Since 64%63 = 1, taking the modulus mod 63 will add all of these together. + ((n & 0x0C30C30C) >> 2) isolates the counts that are shifted by 6k+2 bits, and adds them to the above. + ((n & 0x30C30C30) >> 4) does the same for counts that are shifted by 6k+4 bits. After those additions we have 6 5-bit counters that the %63 can add together all at once.

Upvotes: 2

Related Questions