Improved hamming weight.

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){