0

I came across a StackOverflow answer that gives the following code to efficiently count the number of bits that are set to 1 in a 32-bit int:

int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

But I had lot of issues in understanding this. I couldn't find a link where it's explained properly. Can anyone help me out here in understanding this piece of code, or provide a link which could be more helpful?

Community
  • 1
  • 1
Invictus
  • 4,028
  • 10
  • 50
  • 80
  • 1
    possible duplicate of [How do I count the number of zero bits in an integer?](http://stackoverflow.com/questions/4244274/how-do-i-count-the-number-of-zero-bits-in-an-integer) – Greg Hewgill Mar 01 '12 at 18:02
  • 2
    You should write down the binary representation of the constants used in the original code and see what it does if you run it, on paper. You do know what operators like `>>` do, right? – Mr Lister Mar 01 '12 at 18:02
  • @MrLister right Shift operator – Invictus Mar 01 '12 at 18:03
  • 3
    Explanation: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel – Adam Rosenfield Mar 01 '12 at 18:12
  • possible duplicate of [Best algorithm to count the number of set bits in a 32-bit integer?](http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer) – Bo Persson Mar 01 '12 at 20:19

1 Answers1

1

Answering somewhat indirectly: a great reference on how bit twiddling routines like this (and hundreds of others) work is the book "Hacker's Delight" by Henry Warren. I highly recommend it -- it belongs on every programmer's bookshelf. http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654

Perry
  • 4,363
  • 1
  • 17
  • 20