Empirical
bitset_utils.h
Go to the documentation of this file.
1 
11 #ifndef EMP_BITSET_UTILS_H
12 #define EMP_BITSET_UTILS_H
13 
14 #include "functions.h"
15 
16 namespace emp {
17 
19  template <int NUM_BITS>
20  constexpr uint32_t UIntMaskFirst() { return (UIntMaskFirst<NUM_BITS-1> << 1) | 1; }
21 
23  template <>
24  constexpr uint32_t UIntMaskFirst<0>() { return 0; }
25 
27  constexpr size_t ByteCount[256] = {
28  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
29  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
30  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
31  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
32  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
33  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
34  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
35  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
36  };
37 
39  inline constexpr size_t count_bits(uint64_t val) {
40  return
41  ByteCount[ val >> 56 ] +
42  ByteCount[ (val >> 48) & 0xFF ] +
43  ByteCount[ (val >> 40) & 0xFF ] +
44  ByteCount[ (val >> 32) & 0xFF ] +
45  ByteCount[ (val >> 24) & 0xFF ] +
46  ByteCount[ (val >> 16) & 0xFF ] +
47  ByteCount[ (val >> 8) & 0xFF ] +
48  ByteCount[ val & 0xFF ];
49  }
50 
52  inline constexpr size_t count_bits(uint32_t val) {
53  return
54  ByteCount[ val >> 24 ] +
55  ByteCount[ (val >> 16) & 0xFF ] +
56  ByteCount[ (val >> 8) & 0xFF ] +
57  ByteCount[ val & 0xFF ];
58  }
59 
61  inline constexpr size_t find_bit(const uint64_t & val) { return count_bits( (~val) & (val-1) ); }
62 
64  inline constexpr size_t find_bit(const uint32_t & val) { return count_bits( (~val) & (val-1) ); }
65 
66  /*
67  // Returns the position of the first set (one) bit or a -1 if none exist.
68  template <size_t BITS>
69  int find_bit(const std::bitset<BITS> & in) {
70  int offset = 0;
71  uint64_t tmp_bits = 0ULL;
72  while (offset < BITS && ((tmp_bits = (in >> offset).to_ullong()) == 0ULL)) {
73  offset += 64;
74  }
75  return tmp_bits ? find_bit(tmp_bits) + offset : -1;
76  }
77 
78  template <size_t BITS1, size_t BITS2>
79  std::bitset<BITS1+BITS2> concat_bits(std::bitset<BITS1> in1, std::bitset<BITS2> in2) {
80  constexpr int BITS_OUT = BITS1 + BITS2; // How many bits are in the output?
81  constexpr int FULL_ULLS1 = BITS1 >> 6; // How many 64-bit groups of bits fit into in1?
82  constexpr int FULL_ULLS2 = BITS2 >> 6; // How many 64-bit groups of bits fit into in2?
83  // constexpr int EXTRA_BITS1 = BITS1 & 63; // How many bits are leftover in BITS1?
84  constexpr int EXTRA_BITS2 = BITS2 & 63; // How many bits are leftover in BITS2?
85  std::bitset<BITS_OUT> out_bits;
86 
87  // Copy over in1...
88  for (int i = FULL_ULLS1; i >= 0; --i) {
89  out_bits <<= 64; // Make room for the next group of bits.
90  out_bits |= (in1 >> (i*64)).to_ullong(); // Put them in place.
91  }
92  }
93 
94  template <size_t BITS>
95  constexpr std::bitset<BITS> mask_bit(uint32_t id) {
96  return (std::bitset<BITS>(1)) << id;
97  }
98 
99  template <size_t BITS>
100  constexpr std::bitset<BITS> mask_pattern(size_t start, size_t step, size_t end) {
101  return mask_bit<BITS>(start) | std::bitset<BITS>(mask_pattern<BITS*(start<end)>(start+step,step,end));
102  }
103 
104  template <>
105  constexpr size_t mask_pattern<0>(size_t start, size_t step, size_t end) {
106  return 0;
107  }
108  */
109 }
110 
111 #endif
constexpr size_t ByteCount[256]
How many bits are set to one in each possible byte?
Definition: bitset_utils.h:27
constexpr size_t count_bits(uint64_t val)
Count the number of bits in a 64-bit unsigned integer.
Definition: bitset_utils.h:39
constexpr uint32_t UIntMaskFirst()
Create a series of a specified number of ones (at compile time) in a uint.
Definition: bitset_utils.h:20
If we are in emscripten, make sure to include the header.
Definition: array.h:37
constexpr size_t find_bit(const uint64_t &val)
Return the position of the first one bit (in a 64-bit unsigned int)
Definition: bitset_utils.h:61
constexpr uint32_t UIntMaskFirst< 0 >()
Create an empty bit mask (all zeros)
Definition: bitset_utils.h:24