How to implement Bitcount using only Bitwise operators?

by

From http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here

c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;

Edit: Admittedly it’s a bit optimized which makes it harder to read. It’s easier to read as:

c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F);
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF);
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF);

Each step of those five, adds neighbouring bits together in groups of 1, then 2, then 4 etc.
The method is based in divide and conquer.

In the first step we add together bits 0 and 1 and put the result in the two bit segment 0-1, add bits 2 and 3 and put the result in the two-bit segment 2-3 etc…

In the second step we add the two-bits 0-1 and 2-3 together and put the result in four-bit 0-3, add together two-bits 4-5 and 6-7 and put the result in four-bit 4-7 etc…

Example:

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

which is equal to 5, which is the correct result

More Related Contents:

  1. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  2. Arithmetic bit-shift on a signed integer
  3. Are the shift operators () arithmetic or logical in C?
  4. What is Bit Masking?
  5. What is CHAR_BIT?
  6. Rounding up to next power of 2
  7. Catch and compute overflow during multiplication of two large integers
  8. Find most significant bit (left-most) that is set in a bit array
  9. Fast computing of log2 for 64-bit integers
  10. Extracting bits with a single multiplication
  11. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  12. Bitwise operators and “endianness”
  13. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  14. Bitfield manipulation in C
  15. Fastest way to clamp a real (fixed/floating point) value?
  16. Casting float to int (bitwise) in C
  17. Compute fast log base 2 ceiling
  18. set the m-bit to n-bit [closed]
  19. Bitshift and integer promotion?
  20. Bit twiddling: which bit is set?
  21. How to define and work with an array of bits in C?
  22. Implementing Logical Right Shift in C
  23. How do I get bit-by-bit data from an integer value in C?
  24. Algorithm to generate bit mask
  25. How does this bitwise operation check for a power of 2?
  26. Check if a number is non zero using bitwise operators in C
  27. Decimal to Binary
  28. C Programming – XOR Bitwise Operation
  29. Order of fields when using a bit field in C
  30. What is bit masking?

Leave a Comment