diff options
| -rw-r--r-- | set_bitsets.c | 20 |
1 files changed, 16 insertions, 4 deletions
diff --git a/set_bitsets.c b/set_bitsets.c index 7eddcfd..f59e61e 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -21,10 +21,22 @@ int nbCells(int n){ //the mathematical ceil function } int nb_one(unsigned long long x) { //the hamming weight of x - int cnt = 0, i; - for(i = 0; i < SCOD; i++) - cnt+= ((x>>i)&1); - return cnt; + assert(SCOD==64); + + //1 + x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); + //2 + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + //4 + x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); + //8 + x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); + //16 + x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF); + //32 + x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF); + + return x; } int set_size(const set s){ |