Counting the number of 1's in an integer C

Question

What is the best way to count the number of 1's in an 32-bit integer x in C without using for or while loops, and without using constants greater than 0xFF?

What I thought of is shifting x 24 to the right and count how many 1's in the shifted integer and store that in a variable count. And then, shifting x 16 to the right and increment count by the number of 1's in the shifted integer, and so on.

So, any ideas of a better solution?

The code heavily relies on implementation defined behaviour, i.e. is not portable. It also can invoke undefined behaviour for too large shift counts on platforms with <25 bit `int`. Shifting signed integers is alwas problematic. Avoid it, unless you can guarantee the sign-bit is not involved (which means: just avoid it). — too honest for this site, Sep 17 '17 at 21:51
By number of ones do you mean the binary representation of the number or the base 10 — Mitch, Sep 17 '17 at 21:53
@Mitchel0022: In a **binary** digital computer everything is encoded binary. And it is obviously not BCD. — too honest for this site, Sep 17 '17 at 21:55
It is a duplicate of https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — kamarkiewicz, Sep 17 '17 at 21:55
@Olaf In a binary digital computer sometimes you want to count the number of ones that would appear in other bases as well — Mitch, Sep 17 '17 at 21:56
As just for/while loops are mentioned: is recursion an option? — Stephan Lechner, Sep 17 '17 at 22:00
Possible duplicate of [How to count the number of set bits in a 32-bit integer?](https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer) — Petr Skocik, Sep 17 '17 at 22:02
@StephanLechner: No, I am just allowed to use those operators (! ˜ & ˆ | + << >>) — Hammam A, Sep 17 '17 at 22:02
This requirement, with it's unreasonable constraints, is of negative use to future SO users/visitors. — Martin James, Sep 17 '17 at 22:24
you may want to take a look at Warren's book "Hacker's Delight", it has a chapter on counting bits. — thurizas, Sep 17 '17 at 22:34
@Mitchel0022: In a real world application? Most unlikely. And the code shown _obviously_ does not. — too honest for this site, Sep 17 '17 at 22:37
"I am just allowed to use those operators" - You are aware you have to state it is a homework dump, are you? Read [ask] and the linked posts. — too honest for this site, Sep 17 '17 at 22:38
What is "better"? Speed? Size? Power consumtion? Distribution of 0/1 bits in the machine code? — too honest for this site, Sep 17 '17 at 22:39

score 1 · Answer 1 · 2017-09-17T22:35:19.023

1

You can tabulate the number of 1's in all d bits numbers. This takes a table of 2^d entries, each not exceeding the value d (<255).

Now you can cut your number in slices of d bits and lookup the counts for all slices.

A good compromise between space/number of operations is probably with d=4 (8 slices, table size=16).

edited Sep 17 '17 at 22:35

answered Sep 17 '17 at 21:56

That is not necessarily better, but worse. – too honest for this site Sep 17 '17 at 22:38
@Olaf: what are you talking about ? – Sep 17 '17 at 22:43
Most likely about what you wrote I'd say. – too honest for this site Sep 17 '17 at 23:25
@YvesDaoust Don't worry about Olaf. I agree with you about your "good compromise" -- that's the technique I prefer, too. – Steve Summit Sep 18 '17 at 04:34

Counting the number of 1's in an integer C

1 Answers1