Bit Counting in C similar to bit twiddling hack

Question

I need to make a routine that counts bits in a word that does not involve loops (only bit operations), and does not use large constants.

int x = 0xFFFFFFFF;
x += (~((x >> 1) & 0x55555555)+1);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0F0F0F0F);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003F);

This I found on bit twiddling hacks, but the largest constant I can use is 0xFF... Not sure how to do this otherwise.

Thanks folks.

You can easily go from `0xff` to `0xffffffff` with only bitwise shift and or. Same with the other literal constants. — Some programmer dude, Apr 10 '12 at 16:31
Best to make `x` type `uint32_t` (explicitly exactly 32 bits) or `unsigned long` (32 or more bits), since otherwise it might only be 16 bits. — torek, Apr 10 '12 at 20:02
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) — phuclv, Jun 05 '17 at 12:35
@JesusRamos as long as the answer is helpful to the author, does it matter if this is homework or interview? this is nonsense! — FaceBro, Jun 05 '17 at 13:38

score 4 · Answer 1 · answered Apr 10 '12 at 16:36

4

You can for example use a constant array COUNTS[16] which is the number of set bits in the binary representation of numbers from 0 to 15. Then:

static inline int byte_count (int x) {
  static const int COUNTS[16] = { 0, 1, 1, 2, 1, /* fill in the rest manually */ };
  return COUNTS[x & 15] + COUNTS[x >> 4];
}

int count(int x) {
  return byte_count(x >> 24) + byte_count((x >> 16) & 255) + byte_count((x >> 8) & 255) + byte_count(x & 255);
}

No loops and no constants larger than 255.

answered Apr 10 '12 at 16:36

zvrba

24,186
3
55
65

It would be nice if you explain whats happening here. – Pavan Manjunath Apr 10 '12 at 16:43
Why don't you use a lookup table with 256 entries? If you use `char` instead of `int`, it won't have much of an impact. – onemasse Apr 10 '12 at 16:49
@onemasse Smaller table = less cache pollution (4*16=64 bytes=1 cache line). – zvrba Apr 10 '12 at 19:55
@PavanManjunath No need for an explanation, just work it out with pencil and paper. – zvrba Apr 10 '12 at 19:56

score 3 · Answer 2 · edited Jun 20 '20 at 09:12

3

Using your algorithm:

int x = 0xFF;
x |= (x << 8);  // x = 0xFFFF
x |= (x << 16); // x = 0xFFFFFFFF

and then the rest of the code - provided it works.

Recursive solution:

int foo ( int x )
{
    if ( x == 0 )
        return 0;
    return (x & 1) + foo ( x/2 );
}

edited Jun 20 '20 at 09:12

Community

1
1

answered Apr 10 '12 at 16:34

Luchian Grigore

253,575
64
457
625

phuclv · Answer 3 · 2017-06-05T12:35:48.043

0

your question is already answered here

int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

edited Jun 05 '17 at 12:35

answered Jul 28 '13 at 05:17

phuclv

37,963
15
156
475

Bit Counting in C similar to bit twiddling hack

3 Answers3

Using your algorithm:

Recursive solution:

Linked