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?

Answer 1

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...

Answer 2

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;
}

Answer 3

You can do 32 minus the number of bits set.

Answer 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.

Answer 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.

Answer 6

I'm surprised no one has mentioned this one:

int num_zero_bits = __builtin_popcount(~num);

This will give the number of zero bits in num when used with GCC.

Answer 7

By far the most obvious solution is a lookup table.

/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }

Answer 8

There is a great book for this kind of stuff : Hacker's Delight (yeah, the name sucks : it has nothing to do with security but exclusively bit-twiddling). It provides several algorithms to count '1' bits, the best can also be found here (although the book has explanations that this website doesn't).

Once you know the '1' bits count, just subtract it to the number of bits in your type representation.

Answer 9

With c++20, you can use the standard library function bit_width and popcountto achieve this:

#include <bit>
#include <cstdint>
#include <iostream>
 
int main()
{
    uint32_t i = 276;
    std::cout << std::bit_width(i) - std::popcount(i) << '\n'; // output: 6
}

Answer 10

Do a one's compliment then count the 1s.

count_zero_bits( x ) = count_one_bits( ~x );

Implement the code to count the ones.

template< typename I > 
int count_one_bits( I i )
{
   size_t numbits = 0;
   for( ; i != 0; i >>= 1 )
   {
      numbits += i&1;
   }
}

although there is an issue with my function if i is a negative number because >> will put 1 bits into the right hand side so you will get a never-terminating loop. If there is a templated way to enforce an unsigned type that would be ideal.

Once you have that then:

template< typename I > int count_zero_bits( I i )
{
   return count_one_bits( ~i );
}

will work.

Answer 11

According to me , the simplest way to get the zero bit count in a positive integer is the following piece of code.

int get_zero_bit_count(int num)
{
    int cnt = 0;

    while(num > 0)
        {
            int and_num = num & 1;

            if (and_num != num) cnt++;

            num >>= 1; 
        }

        return cnt;
    }

This piece of code is easy to understand and is selp explainatory . This works well for positive integers.

Answer 12

Expanding on ronag's answer, which other users have mentioned leads to wrong results (his algorithm works only up to a value of x = 15), here is an updated version of the algorithm:

uint8_t count_1bits(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
    return x & 0x3F;
}

uint8_t count_0bits(uint32_t x)    {
    return 32 - count_1bits(x);
}

The explanation of the first line from ronag is correct, however, the remaining lines are using a different approach. In the first line, through the shifting and subtracting, each 2-bit pair will contain the number of bits that were set in that pair in the original number. The rest of the lines recursively fold those numbers together by adding the lsb of each 2n-bit group to the msb of that pair shifted by n, so that the 2n-bit group contains the number of bits that was set in that group in the original number:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number)
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111
= 0110 + 0111
= 1101

The above algorithm works for 32 bit integers, but can easily be adapted by changing the constants to the correct bit-length so that the pattern stays the same (e.g. 0x5555... = 0101..., 0x0f0f... = 00001111... etc.) and adding/removing the appropriate shifts

Answer 13

#include <bits/stdc++.h>
using namespace std;
#define ll long long int


int main() {
    ll a;
    cin>>a;
    ll ones=__builtin_popcountll(~a);
    ll zero=__builtin_clzll(a);
    ll num=abs(ones-zero);
    cout<<num<<"\n";
    return 0;
}

with the help of builtin gcc functions i.e. popcount(counts number of set bit) and clz(count number of leading zero's) we can calculate the number of zero bit in an integer

you can read about them here https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html, https://www.geeksforgeeks.org/builtin-functions-gcc-compiler/