diff options
| author | Vladimir Byko-Ianko <bykoianko@gmail.com> | 2017-01-31 08:49:19 +0300 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2017-01-31 08:49:19 +0300 |
| commit | ae808a8825c2a513b02d95315215cdc2fa9fcd12 (patch) | |
| tree | 011af2528e4886cecc535b4bf8eab69e3b7868aa | |
| parent | 417085a6c9553a0d34ee0f174f47a8b3e31f359c (diff) | |
| parent | 64fe56bd9f4127bbe89da9397aa97400a5c17172 (diff) | |
Merge pull request #5307 from ygorshenin/fix-popcount64beta-597
[base] A speedup for PopCount64.
| -rw-r--r-- | base/bits.hpp | 10 |
1 files changed, 4 insertions, 6 deletions
diff --git a/base/bits.hpp b/base/bits.hpp index f767c85d55..ad0eeac236 100644 --- a/base/bits.hpp +++ b/base/bits.hpp @@ -63,12 +63,10 @@ namespace bits inline uint32_t PopCount(uint64_t x) noexcept { - x = (x & 0x5555555555555555) + ((x & 0xAAAAAAAAAAAAAAAA) >> 1); - x = (x & 0x3333333333333333) + ((x & 0xCCCCCCCCCCCCCCCC) >> 2); - x = (x & 0x0F0F0F0F0F0F0F0F) + ((x & 0xF0F0F0F0F0F0F0F0) >> 4); - x = (x & 0x00FF00FF00FF00FF) + ((x & 0xFF00FF00FF00FF00) >> 8); - x = (x & 0x0000FFFF0000FFFF) + ((x & 0xFFFF0000FFFF0000) >> 16); - x = x + (x >> 32); + x = x - ((x & 0xAAAAAAAAAAAAAAAA) >> 1); + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F; + x = (x * 0x0101010101010101) >> 56; return static_cast<uint32_t>(x); } |