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;
>
> for (MASK = 0x1; MASK != 0; MASK <<= 1)
> if ((MASK & i) == 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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Charles Hixson Python 5 10-26-2012 04:30 PM MRAB Python 0 10-25-2012 03:18 PM Scotius Digital Photography 6 07-13-2010 03:33 AM vvcd Computer Support 0 09-17-2004 08:15 PM Ionizer Computer Support 1 01-01-2004 07:27 PM

Advertisments