How do I count the number of zero bits in an integer?

Question

How would i go about finding the number of 'zero' bits in C++. Suppose I have an integer;

int value = 276; 

For which I have the bits 100010100, but how do I count the zeros?

Solution 1

The easiest most naive way is to just iterate over the bits and count:

size_t num_zeroes = 0;

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
  if ((value & (1 << i)) == 0)
    ++num_zeroes;
}

There are all number of better (for different values of "better") ways, but this is quite clear, very terse (code-wise), and doesn't require a bunch of setup.

One micro-optimization that might be considered an improvement is to not compute the mask to test each bit, instead shift the value and always test the rightmost bit:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
  if ((value & 1) == 0)
    ++num_zeroes;
}

Solution 2

If you want efficiency then there is a good implementation in the book "Hackers Delight"

22 instructions branch free.

unsigned int count_1bits(unsigned int x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

unsigned int count_0bits(unsigned int x)
{
    return 32 - count_1bits(x);
}

I'll try to explain how it works. It is a divide-and-conquer algorithm.

(x >> 1) & 0x55555555

Shifts all bits 1 step to the right and takes the least significant bit of every bit pair.

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs)

So basically you will have the following table of all 2 bit permutations.

1. (00 >> 1) & 01 = 00
2. (01 >> 1) & 01 = 00
3. (10 >> 1) & 01 = 01
4. (11 >> 1) & 01 = 01

x - ((x >> 1) & 0x55555555);

Then you subtract these from the non shifted pairs.

1. 00 - 00 = 00 => 0 x 1 bits
2. 01 - 00 = 01 => 1 x 1 bits
3. 10 - 01 = 01 => 1 x 1 bits
4. 11 - 01 = 10 => 2 x 1 bits

x = x - ((x >> 1) & 0x55555555);

So now we have changed every 2 bit pair so that their value is now the number of bits of their corresponding original 2 bit pairs... and then we continue in similar way with 4 bit groups, 8 bit groups, 16 bit groups and final 32 bit.

If you want a better explanation buy the book, there are a lot of good explanation and discussions of alternative algorithms etc...

Solution 3

You can do 32 minus the number of bits set.

Solution 4

If you use GCC, you can try built-in functions:

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)

See GCC Documentation for details.

Solution 5

Kernighan way of counting set bits

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Can be easily adapted for the task given. A number of iterations here is equal to a number of bits set.

I also recommend the link above for various other ways of solving this and others types of bit-related tasks. There also is a single line example of obtaining bit count implemented in macros.

View more solutions

Comments

[visual_learner]

Check here: graphics.stanford.edu/~seander/bithacks.html

[Bojan Komazec]

Try to google for "bit counting"

[mih]

Did you forget about 23 leading zeros? Yeah, yeah, I know it depends on integer representation ;)

[Dmitri]

I spent a fair amount of time looking into optimizing popcount for Tanimoto calculations recently; here is a good summary of several methods: dalkescientific.com/writings/diary/archive/2008/07/05/… Ended up using a 16-bit LUT, it's simple and negligibly slower than the fastest. That's if you care about speed at all.

[R. Martinho Fernandes]

I think that "counting the number of zero bits" is by far a more obvious solution to the problem of "How do I count the number of zero bits in an integer?"

[BЈовић]

better to 8*sizeof(int) - (number of set bits), but the suggestion is good

[SysAdmin]

the meaning of the word 'Hacking' or 'Hacker' is misunderstood. It is not just about security. In this context, it just means "clever or quick fix" (See Wikipedia). :)

[R. Martinho Fernandes]

@SysAdmin: unfortunately the damn media twisted the meaning of hack/hacking/hacker into that of crack/cracking/cracker. Some of us still resist, though.

[icecrime]

@SysAdmin: true indeed, but every time I recommend this book I get stupid comments about security :)

[JeremyP]

@VJo: does the C++ standard mandate an 8 bit byte then? Technically, in C you can't assume that sizeof returns the size in 8 bit bytes.

[BЈовић]

@JeremyP You are right. c++ standard, 1.7-1 tells "A byte is at least large enough to contain any member of the basic execution character set and is composed of a contiguous sequence of bits, the number of which is implementation-defined."

[user]

Except count_0bits() assumes that an unsigned int is 32 bits on your platform and compiler of choice...

[ronag]

Indeed. One would need to do separate implementation for 16,32 and 64 bits. Could be done with meta-template programming.

[Kricket]

Another micro-optimization would be to remove the ==0 (and modify the condition a bit), since 0==false and 1==true.

[unwind]

@Kelsey: but that is just silly, the compiler will do that at very low levels of optimizations (or maybe even at none). Much better to keep it for clarity.

[MSalters]

Yup, you'd need CHAR_BIT * sizeof(int) and even that only tells you the size in memory, not how many bits are actually needed for the value representation of int. That you get from std::numeric_limits<int>::digits + std::numeric_limits<int>::is_signed

[Brett Hale]

This is a very useful addition - many important algorithms yield sparse distributions of set bits in very large (multiple word) bit vectors, or matrices.