BitShares-Core  4.0.0
BitShares blockchain implementation and command-line interface software
popcount.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2019 BitShares Blockchain Foundation, and contributors.
3  *
4  * The MIT License
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22  * THE SOFTWARE.
23  */
24 
25 #include <fc/popcount.hpp>
26 
27 namespace fc {
28 
29 #if _MSC_VER || __GNUC__ || __clang__
30 #else
31 uint8_t popcount( uint64_t v )
32 {
33  // Public Domain code taken from http://graphics.stanford.edu/~seander/bithacks.html
34  uint8_t c;
35  static const int S[] = {1, 2, 4, 8, 16, 32};
36  static const uint64_t B[] = {0x5555555555555555, 0x3333333333333333, 0x0F0F0F0F0F0F0F0F,
37  0x00FF00FF00FF00FF, 0x0000FFFF0000FFFF, 0x00000000FFFFFFFF };
38 
39  c = v - ((v >> 1) & B[0]);
40  c = ((c >> S[1]) & B[1]) + (c & B[1]);
41  c = ((c >> S[2]) + c) & B[2];
42  c = ((c >> S[3]) + c) & B[3];
43  c = ((c >> S[4]) + c) & B[4];
44  return ((c >> S[5]) + c) & B[5];
45 }
46 #endif
47 
48 uint8_t popcount( const uint128_t& v )
49 {
50  return popcount( static_cast<uint64_t>(v >> 64) )
51  + popcount( static_cast<uint64_t>(v & 0xffffffffffffffffULL) );
52 }
53 
54 } // namespace fc
Definition: api.hpp:15
uint8_t popcount(uint64_t v)
Definition: popcount.cpp:31