diff options
| author | Mendes Oulamara <oulamara@clipper.ens.fr> | 2013-12-05 09:21:22 +0100 |
|---|---|---|
| committer | Mendes Oulamara <oulamara@clipper.ens.fr> | 2013-12-05 09:21:22 +0100 |
| commit | 50b5699f9b6d887c31e546168d9e588b36e3f876 (patch) | |
| tree | 6f984a6a671866a06ebaaaf4566f4b73fe677eb0 /set_bitsets.c | |
| parent | 42af2c9cb9c86ff7d92062d8a535015b852647e6 (diff) | |
| parent | cbffb4f8d60a8516b23aae1bdf07197787ddce2c (diff) | |
| download | AlgoProg-Projet-50b5699f9b6d887c31e546168d9e588b36e3f876.tar.gz AlgoProg-Projet-50b5699f9b6d887c31e546168d9e588b36e3f876.zip | |
Merge branch 'master' of /users/13/info/oulamara/Work/../../auvolat/boulot/AlgoProg-Projet
Diffstat (limited to 'set_bitsets.c')
| -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..4ac8462 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); // mask : 0101010101... + //2 + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); // mask : 001100110011... + //4 + x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); // mask : 000011110000.... + //8 + x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); // etc. + //16 + x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF); + //32 + x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF); + + return x; } int set_size(const set s){ |