This code below implements population count for 4 64-bit integers. (Tested with GCC 4.4.1 64-bit Linux). This becomes part of BM 3.6.3 (when SourceForge recovers from its (I hope temporary) down).

inline

unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y,

bm::id64_t u, bm::id64_t v)

{

const bm::id64_t m1 = 0x5555555555555555;

const bm::id64_t m2 = 0x3333333333333333;

const bm::id64_t m3 = 0x0F0F0F0F0F0F0F0F;

const bm::id64_t m4 = 0x000000FF000000FF;

x = x - ((x >> 1) & m1);

y = y - ((y >> 1) & m1);

u = u - ((u >> 1) & m1);

v = v - ((v >> 1) & m1);

x = (x & m2) + ((x >> 2) & m2);

y = (y & m2) + ((y >> 2) & m2);

u = (u & m2) + ((u >> 2) & m2);

v = (v & m2) + ((v >> 2) & m2);

x = x + y;

u = u + v;

x = (x & m3) + ((x >> 4) & m3);

u = (u & m3) + ((u >> 4) & m3);

x = x + u;

x = x + (x >> 8);

x = x + (x >> 16);

x = x & m4;

x = x + (x >> 32);

return x & 0x000001FF;

}

## No comments:

## Post a Comment