Velocity Reviews > Bit count of an integer

# Bit count of an integer

James Harris
Guest
Posts: n/a

 11-05-2007
On 5 Nov, 15:33, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> I read some old posts, they did this task in very different ways. How
> is the following one?
>
> Thank you for your time.
>
> /
> ************************************************** ******************************
> * Count the bit set in an integer. eg. integer: 0x01101011, bitcount:
> 5
>
> ************************************************** *****************************/
>
> int bitcount(int i)
> {
> unsigned int cnt = 0, MASK;
>
> cnt++;
> return cnt;

Since others are going for speed how about the following. (The C may
not be completely correct.) It combines fast lookup with a small
table. There is a reasonable chance that the looked up value will be
in cache (which would be better if there were some way to align the
array).

int nibble_bits[] = { /* The number of bits in each nibble 0 to 15 */
0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4
}

int bitcount (int i) {
int bits_set = 0;

for (; i; i >>= 4) {
bits_set += nibble_bits[i & 0xf];
}
return bits_set;
}

Ark Khasin
Guest
Posts: n/a

 11-06-2007
Ben Pfaff wrote:

> I have timed the following in the past as being quite fast. It
> is branch-free:
>
> /* Compute and return the the number of 1-bits set in X. */
> int
> count_one_bits_32 (uint32_t x)
> {
> x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
> x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
> x = (x >> 16) + (x & 0xffff);
> x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
> return (x >> + (x & 0x00ff);
> }
>

Just for kicks, here's yet another size-specific (and also
generalizable) version. Here multiplication does bit tallying in pruned
bitmaps.
Whether it's better or worse probably depends on the instruction set.
#define ONES 0x11111111U
unsigned mybits(uint32_t x)
{
unsigned count;
count = ((x & ONES) * ONES) >> 28;
count += (((x>>1) & ONES) * ONES) >> 28;
count += (((x>>2) & ONES) * ONES) >> 28;
count += (((x>>3) & ONES) * ONES) >> 28;
return count;
}

--
Ark