Number of 1 bits

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has. For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

Brute force solution:
Iterate 32 times, each time determining if the ith bit is a ‘1’ or not. This is probably the easiest solution, and the interviewer would probably not be too happy about it. This solution is also machine dependent (You need to be sure that an unsigned integer is 32-bit). In addition, this solution is not very efficient too, as you need to iterate 32 times no matter what.

Lookup table solution:
If you need maximum speed, lookup table is the way to go. Keep in mind that you need a huge memory for this. Depending on the maximum bits an integer has, you might need up to 4GB of memory to store the table!

Best solution:
Hint: Remember my last post about making use x & (x-1) to determine if an integer is a power of two? Well, there are even better uses for that! Remember every time you perform the operation x & (x-1), a single 1 bit is erased?

The following solution is machine independent, and is quite efficient. It runs in the order of the number of 1s. In the worst case, it needs to iterate 32 times (for a 32-bit integer), but a case such as the number ‘8’ would only need to iterate 1 time.

More Bit Hacking Fun:
If you would like to explore more about bit hacking, I recommend these resources to get you started:

» Low Level Bit Hacks You Absolutely Must Know
» Bit Twiddling Hacks

The first one is beginner-friendly, and teaches you the basic but useful bit hacks you encounter often. The latter one is more difficult and has quite some clever bit hacks. Some of the bit hacks contain just one line of code, which is amazing.

EDIT: (More Bit Twiddling Fun)

Try this question from Google CodeJam 2010 for more bit twiddling fun.
» Google CodeJam 2010 Qualification Round Problem A: Snapper Chain

VN:F [1.9.22_1171]
Rating: 4.9/5 (9 votes cast)
Number of 1 bits, 4.9 out of 5 based on 9 ratings

16 thoughts on “Number of 1 bits

  1. Andrew Dalke

    "and is as efficient as it can be."

    Have you timed it? My tests for 64 bit integers showed it was about 1/4th the speed of other algorithmic population count algorithms and about 1/7th the speed of a lookup table. (See the results for "Wegner/Kernigan" at
    http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html ).

    The disadvantage of the algorithm you quote here is likely the amount of branching the CPU needs to do. Now, it is highly data dependent and if you have a lot of 0 words then your code might be the fastest, but if there's a lot of 0s then you're using the wrong data structure.

    VA:F [1.9.22_1171]
    0
  2. 1337c0d3r

    @Andrew:
    Thanks for that interesting link. I have just corrected my post to mean "It is efficient," but is not the most efficient one. If there's a lot of 0s, isn't this algorithm more efficient? This is because the number of time it loops is based on the number of 1s.

    VA:F [1.9.22_1171]
    0
  3. HX

    how about using log() function?

    while (true)
    {
    int i = log(x);
    x = x – 2**i;
    if (x <= 0)
    break;
    else
    number_of_1++;
    }

    VA:F [1.9.22_1171]
    0
  4. coollpe

    What about bitset? In fact it may be faster than any kind of hacks above if it’s compiled on a machine that supports POPCNT.

    std::bitset b(x);
    return b.count();

    __builtin_popcount(x) can do similar job.

    It’s actually better than any awful code above because it leaves room for optimization by CPU.

    VA:F [1.9.22_1171]
    0
  5. Pingback: Must read problems of LeetCode | What I learn, I blog !

  6. bradyfang

    VA:F [1.9.22_1171]
    +2
  7. whihathac

    VA:F [1.9.22_1171]
    0
  8. Ralph

    a more efficient one in Java (hint: divide and conquer)

    VN:F [1.9.22_1171]
    +1

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*