2007-11-06

## Binary Numbers: Counting Bits

Posted by scvalexIn 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; }

This isn’t bad and works in **O(lg(n))** 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.

##### Sparse ones algorithm

This solution relies on the following observation:

`22`

_{10} = 00010110_{2}

22 - 1 = 21_{10} = 00010101_{2}

22 AND 21 = 00010100

Notice what happened: by logically ANDing *22* and *21*, you get a number whose binary representation is the same as *22* but with the last *1* flipped to *0*.

The idea behind this algorithm is to logically AND *n* and *n - 1* until *n* is *0*. The number of times necessary to do this will the the number of *1* 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 <stdio.h> /* 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; }

That’s it. If you’re intrested in a few more (slightly esoteric) algorithms, see this article.

Good luck. Always open to comments.