diff options
| author | Quentin Carbonneaux <quentin.carbonneaux@yale.edu> | 2016-04-05 15:01:51 -0400 |
|---|---|---|
| committer | Quentin Carbonneaux <quentin.carbonneaux@yale.edu> | 2016-04-05 15:01:51 -0400 |
| commit | f6bd53d2adfcd6e0abcbb2070759ca0241d5d7b7 (patch) | |
| tree | 59252153daca2527b7bd466a3fba2358dff10856 /util.c | |
| parent | 7d37d0a7a49dca24db2dd5d8a7e0badd62de6199 (diff) | |
| download | roux-f6bd53d2adfcd6e0abcbb2070759ca0241d5d7b7.tar.gz | |
speedup bscount()
Diffstat (limited to 'util.c')
| -rw-r--r-- | util.c | 19 |
1 files changed, 15 insertions, 4 deletions
diff --git a/util.c b/util.c index fb85dc1..51d7e58 100644 --- a/util.c +++ b/util.c @@ -239,16 +239,27 @@ bsinit(BSet *bs, uint n) bs->t = alloc(n * sizeof bs->t[0]); } +MAKESURE(NBit_is_64, NBit == 64); +inline static uint +popcnt(bits b) +{ + b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555); + b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333); + b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f); + b += (b>>8); + b += (b>>16); + b += (b>>32); + return b & 0xff; +} + uint bscount(BSet *bs) { - uint i, j, n; + uint i, n; n = 0; for (i=0; i<bs->nt; i++) - for (j=0; j<NBit; j++) - if (bs->t[i] & BIT(j)) - n++; + n += popcnt(bs->t[i]); return n; } |