summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlex Auvolat--bernstein <auvolat@clipper.ens.fr>2013-12-04 18:07:33 +0100
committerAlex Auvolat--bernstein <auvolat@clipper.ens.fr>2013-12-04 18:07:33 +0100
commit3ab1dd7971402fd2d76d464e4e193132b4a9eb89 (patch)
tree21b699923c17c9336a390633008bf5828260ebf5
parentf7022495daa31b714a73d6bdf6640db7494f1f4c (diff)
downloadAlgoProg-Projet-3ab1dd7971402fd2d76d464e4e193132b4a9eb89.tar.gz
AlgoProg-Projet-3ab1dd7971402fd2d76d464e4e193132b4a9eb89.zip
Improved hamming weight.
-rw-r--r--set_bitsets.c20
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){