# Efficiently counting '1' bits in the first n bits

I have two functions to count the number of set '1' bits in the first offset bits of either a 64 bit number, or a bitmap struct.

After some profiling, particularly the latter is quite a bottleneck in our system.

What can we do to make it faster?

#define POPCOUNT16(x) __builtin_popcount(x)
#define POPCOUNT64(x) __builtin_popcountl(x)

static __always_inline __constant int32 count64(int64 const bitmap, int32 const offset) {
return offset == 0 ? 0 : POPCOUNT64(bitmap & (0xffffffffffffffffUL << (64 - offset)));
}

typedef struct {
int64 hi;
int16 lo;
} __packed int80;

static __always_inline __constant int32 countBitmap(int80 const bitmap, int32 const offset) {
int32 count = 0;
if (offset > 0) {
count += POPCOUNT64(bitmap.hi & (0xffffffffffffffffUL << (sizeof (bitmap.hi)*8 - MIN(offset, sizeof (bitmap.hi)*8))));
if (offset > sizeof (bitmap.hi)*8)
count += POPCOUNT16(bitmap.lo & ((int16)0xffff << (sizeof (bitmap.hi)*8+sizeof (bitmap.lo)*8 - offset)));
}
return count;
}

• Either I'm confused, or you are. count64() takes an int64 bitmap — how can there be a bitmap.hi? – 200_success Jan 28 '14 at 3:05
• can you guarantee that offset is larger than 0? if so you can eliminate the first branch – ratchet freak Jan 28 '14 at 10:26
• @ratchetfreak Either I have the branch at the call site, or in the function. As it's marked with inline __attribute__((always_inline)), I figured it would make no difference which, so I put it in the function for simplicity. – Max Jan 28 '14 at 12:54

first issue: you hardcode 8 as the number of bits per sizeof unit: portability says it should be CHAR_BIT which may be something else on some architectures

second issue: both members of int80 are signed, only hi should be while lo can be unsigned

if you can guarantee that offset is between 0 and 80 then you don't need to test for 0, and just document that exceeding the bounds is undefined behavior

static __always_inline __constant int32 countBitmap(int80 const bitmap, uint32 const offset) {
int32 count = 0;
if (offset <= sizeof (bitmap.hi)*CHAR_BIT) {
count = POPCOUNT64(bitmap.hi >>> (sizeof (bitmap.hi)*CHAR_BIT - offset));
// logical right shift to do away with the AND
}else{
count = POPCOUNT64(bitmap.hi)+
POPCOUNT16(bitmap.lo >>> (sizeof (bitmap)*CHAR_BIT - offset));
}
return count;
}


here there is only 1 branch compared to the 2 you had before (possibly 3 depending on how MIN was implemented)