Created
December 26, 2023 19:21
-
-
Save apurvanandan1997/b055a822f17f3ec0a866a77b154279de to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Counting bits set, in parallel | |
unsigned int v; // count bits set in this (32-bit value) | |
unsigned int c; // store the total here | |
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers | |
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF}; | |
c = v - ((v >> 1) & B[0]); | |
c = ((c >> S[1]) & B[1]) + (c & B[1]); | |
c = ((c >> S[2]) + c) & B[2]; | |
c = ((c >> S[3]) + c) & B[3]; | |
c = ((c >> S[4]) + c) & B[4]; | |
The B array, expressed as binary, is: | |
B[0] = 0x55555555 = 01010101 01010101 01010101 01010101 | |
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011 | |
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111 | |
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111 | |
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111 | |
We can adjust the method for larger integer sizes by continuing with the patterns for the Binary Magic Numbers, B and S. | |
The best method for counting bits in a 32-bit integer v is the following: | |
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary | |
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp | |
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count | |
The best bit counting method takes only 12 operations, which is the same as the lookup-table method, but avoids the memory and potential cache misses of a table. It is a hybrid between the purely parallel method above and the earlier methods using multiplies (in the section on counting bits with 64-bit instructions), though it doesn't use 64-bit instructions. The counts of bits set in the bytes is done in parallel, and the sum total of the bits set in the bytes is computed by multiplying by 0x1010101 and shifting right 24 bits. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment