In a previous article, I described the basics of binary arithmetic and gave a function to display the binary representation of a number. Here, we’ll look at several ways to count the set (*1*) bits in a number.

First of all, why would you want to count bits? Bitsets. If you use bitsets as a fast set implementation, you might want to find out how many elements there are in the set. I used this in a sudoku programme to memorise which digits can’t be placed in a particular cell. Bit counting functions are also used extensively in graphics (bitmap manipulations).

Here’s *22* in binary:

`00010110`

From the binary representation, it’s obvious that there are *3* set bits and *5* unset bits. How do you count them? I’ll give three methods.

##### Classic, let’s iterate through every bit, solution

The idea behind this is simple: take every bit in the number (*n*) and check if it’s *1*. To do this, you can simply use a variable (*i*):

- initialise
*i*with*1* - check if
*n AND i*is greater than zero and if so, increment a counter - multiply
*i*by*2* - if
*i < n*, go to 2

Here’s the code:

/* Count the ON bits in n using an iterative algorithm */ int bitcount(int n) { int tot = 0; int i; for (i = 1; i <= n; i = i<<1) if (n & i) ++tot; return tot; } [/sourcecode] This isn't bad and works in <strong>O(lg(n))</strong> time, but if you know (you probably will) if the number is made up mostly of ones or zeros, use one of the following algorithms. <h5>Sparse ones algorithm</h5> This solution relies on the following observation: <code>22<sub>10</sub> = 00010110<sub>2</sub> 22 - 1 = 21<sub>10</sub> = 00010101<sub>2</sub> 22 AND 21 = 00010100 </code> Notice what happened: by logically ANDing <em>22</em> and <em>21</em>, you get a number whose binary representation is the same as <em>22</em> but with the last <em>1</em> flipped to <em>0</em>. The idea behind this algorithm is to logically AND <em>n</em> and <em>n - 1</em> until <em>n</em> is <em>0</em>. The number of times necessary to do this will the the number of <em>1</em> bits. Here's the code: /* Counts the ON bits in n. Use this if you know n is mostly 0s */ int bitcount_sparse_ones(int n) { int tot = 0; while (n) { ++tot; n &= n - 1; } return tot; }

Why call it *sparse ones*? Look at the algorithm, and apply it to a few numbers on a piece of paper. You’ll notice that you go through the inner loop the *x* times, where *x* is the number of *1s* in the number. So the time is **O(x)**, and it’s best to use it if there are **few ones** in the number.

##### Dense ones algorithm

But what if your number is mostly *1*? The solution is obvious: flip every bit in *n*, then apply the sparse ones algorithm:

/* Counts the ON bits in n. Use this if you know n is mostly 1s */ int bitcount_dense_ones(int n) { int tot = 0; n ^= (unsigned int)-1; while (n) { ++tot; n &= n - 1; } return sizeof(int) * 8 - tot; }

##### Full source

Here’s the full C source to the programme (bit.c):

**NOTE**: Source is mangled by WordPress. Don’t copy-paste; download the file.

#include

/* Print n as a binary number */

void printbits(int n) {

unsigned int i, step;

if (0 == n) { /* For simplicity’s sake, I treat 0 as a special case*/

printf(“0000”);

return;

}

i = 1<>= 4; /* In groups of 4 */

while (step >= n) {

i >>= 4;

step >>= 4;

}

/* At this point, i is the smallest power of two larger or equal to n */

while (i > 0) {

if (n & i)

printf(“1”);

else

printf(“0”);

i >>= 1;

}

}

/* Count the ON bits in n using an iterative algorithm */

int bitcount(int n) {

int tot = 0;

int i;

for (i = 1; i <= n; i = i<<1)
if (n & i)
++tot;
return tot;
}
/* Counts the ON bits in n. Use this if you know n is mostly 0s */
int bitcount_sparse_ones(int n) {
int tot = 0;
while (n) {
++tot;
n &= n - 1;
}
return tot;
}
/* Counts the ON bits in n. Use this if you know n is mostly 1s */
int bitcount_dense_ones(int n) {
int tot = 0;
n ^= (unsigned int)-1;
while (n) {
++tot;
n &= n - 1;
}
return sizeof(int) * 8 - tot;
}
int main(int argc, char *argv[]) {
int i;
for (i = 0; i < 23; ++i) {
printf("%d = ", i);
printbits(i);
printf("\tON bits: %d %d %d", bitcount(i), bitcount_sparse_ones(i), bitcount_dense_ones(i));
printf("\n");
}
return 0;
}
[/sourcecode]
That's it. If you're intrested in a few more (slightly esoteric) algorithms, see this article.

Good luck. Always open to comments.

2011-02-14 at 8:13

Lookup tables?

byte counts[256] =

2011-02-14 at 8:14

Hmm… My last bit of text was cut off there.

“Since the lookup values won’t change over time, you can pre-compute them and throw them in your source code.”

2011-02-14 at 8:19

I just realized that lookup tables require space in L1 cache instead of working directly inside registers. Depending on the programming language and the optimizations in play, my suggestion may not be ideal.

2011-10-06 at 12:58

This helped so much, thank you thank you thank you!

2011-11-02 at 12:47

Adding my solution below

while(p!=0)

{

if(p & 0x0001)

{

count++;

}

p= p >> 1;

}

Count will have the count of 1s.

2012-05-19 at 21:52

website developer…[…]Binary Numbers: Counting Bits « Computer programming[…]…

2013-06-18 at 17:46

Hello,

Great article! I was just curious about the practical applications of this algorithm. Why would it be useful to know the number of set bits in a binary number?

2013-08-12 at 23:07

It is sometimes necessory to know the values of 0s and 1s, even there positions as bit positions might be associated with the options. this is mostly used in embedded applications where you have limited RAM & NVM. For example a device can work with 8 configuration then I would not want to set 8 diffrent variables and check each one Instead I shall assign each bit for each configuration. I might also be intrested in how many configurations are “on” for that particular device.

2013-10-21 at 0:06

Good to know. How to implement the algorithm in a x toy machine?

2016-01-09 at 17:51

i = i<<1. What does this mean?