Set bit count in a binary number using C

Question

I have got a binary number of length 8 for eg 00110101 There are 8 bits set. I need a fast bit count to determine the number of set bits. Running the algo like this x=x&(x-1) will limit it to the number of set bits in the number contains but I am not very sure as to how to use it.A little help would be appreciable!!

And... http://gurmeet.net/puzzles/fast-bit-counting-routines/ — MByD, Aug 09 '11 at 15:26
Are you looking for the [hamming weight](http://en.wikipedia.org/wiki/Hamming_weight)? — GWW, Aug 09 '11 at 15:27
http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer — Mike Lorenz, Aug 09 '11 at 15:28

Paul · Accepted Answer · 2011-08-09T15:39:08.643

4

This x=x&(x-1) removes the lowest set bit from the binary string. If you count the number of times you remove the lowest bit before the number becomes 0, you'll get the number of bits that were set.

char numBits(char x){
    char i = 0;
    if(x == 0)
        return 0;
    for(i = 1; x &= x-1; i++);
    return i;
}

edited Aug 09 '11 at 15:39

answered Aug 09 '11 at 15:32

Paul

139,544
27
275
264

score 3 · Answer 2 · answered Aug 09 '11 at 15:41

doing x = x & (x-1) will remove the lowest bit set. So in your case the iterations will be performed as,

loop #1: 00110101(53) & 00110100(52) = 00110100(52) :: num bits = 1

loop #2: 00110100(52) & 00110011(51) = 00110000(48) :: num bits = 2

loop #3: 00110000(48) & 00101111(47) = 00100000(32) :: num bits = 3

loop #3: 00100000(32) & 00011111(31) = 00000000( 0) :: num bits = 4

The number of iterations allowed will be the total number of bits in the given number.

score 1 · Answer 3 · answered Dec 11 '19 at 16:29

I have this code snippet works with unsigned integer only: Hope this helps.

uint G = 8501; //10 0001 0011 0101
uint g = 0;

for (int i = 0; i < 32; i++)
{
  g += (G << (31 - (i % 32))) >> 31;
}

Console.WriteLine(g); //6

score 1 · Answer 4 · answered Aug 09 '11 at 15:35

1

US Patent 6,516,330 – Counting set bits in data words

(I only invented it -- don't ask me to explain it.)

answered Aug 09 '11 at 15:35

Hot Licks

47,103
17
93
151

vine'th · Answer 5 · 2011-08-18T04:56:40.760

The method described in the question (generally ascribed to K&R ) has the complexity of n, where n is the number of bits set in the number.

By using extra memory we can bring this to O(1):

Initialize a lookup table with the number of bit counts (compile-time operation) and then refer to it; You can find the method here : Counting bits set by lookup table

You can find a detailed discussion of different methods in Henry S. Warren, Jr.(2007) "The Quest for an Accelerated Population Count", Beautiful Code pp.147-158 O'Reilly

score 0 · Answer 6 · answered Aug 09 '11 at 15:33

Depending on how you count the set bits - the number of really set bits are 4 in our case; the bit-width (which I hereby define as the number of the highest bit set plus 1) is 6 (as you need 6 bits to represent your number). The latter one can be determined with

char highestbit (uint32_t num)
{
    char i;
    for (i = 0; i < sizeof(num)*8; i++) {
        if ((1L << i) > num) {
            return i;
        }
    }
    return sizeof(num)*8;
}

(untested)

score 0 · Answer 7 · answered Aug 09 '11 at 15:46

0

x := (x and $55555555) + ((x shr 1) and $55555555); 
x := (x and $33333333) + ((x shr 2) and $33333333); 
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); 
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); 
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);

Taken from matrix67's blog, which is in Chinese.

answered Aug 09 '11 at 15:46

wecing

534
1
3
19

Which looks suspiciously like the above patent. – Hot Licks Aug 10 '11 at 20:37
@Daniel R Hicks. I hope for your sake the above does not correspond to your patented method. The above method is also described as: [Counting bits set in parallel](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel), the quoted references pre-date your patent application. – NealB Aug 17 '11 at 18:05
As with most software patents, the devil is in the details. The attorneys add enough qualifiers to chisel out a "unique" invention (though in this case I didn't really want to go forward with the patent but the other inventor insisted). I have, however, authored several patents that I'm relatively confident are "clean", including 5,001,477 – Encoding variable length and null data while preserving sort sequence, and I've had a couple of others that were clearly "unique" and "new" rejected by patent examiners who had a bug up their arse. – Hot Licks Aug 17 '11 at 19:04

Set bit count in a binary number using C

7 Answers7