BitArray.h 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127
  1. #ifndef BITARRAY_H
  2. #define BITARRAY_H
  3. #include <iostream>
  4. #include "utils/StringBuffer.h"
  5. template<int N, int BITS>
  6. class BitArray final {
  7. static constexpr int INT_BITS = sizeof (int) * 8;
  8. static_assert(BITS >= 1, "each bit array element must have at least one bit");
  9. static_assert(BITS <= INT_BITS, "each bit array element can have at most as much bits as an int");
  10. static constexpr int MASK = (1 << BITS) - 1;
  11. static constexpr int LENGTH = (N * BITS) / INT_BITS + (((N * BITS) % INT_BITS) > 0);
  12. static constexpr bool ALIGNED = (INT_BITS % BITS) == 0;
  13. constexpr static int getDivideBits() {
  14. int c = 0;
  15. int i = INT_BITS - 1;
  16. while(i > 0) {
  17. i >>= 1;
  18. c++;
  19. }
  20. return c;
  21. }
  22. static constexpr int DIVIDE_BITS = getDivideBits();
  23. int data[LENGTH];
  24. static int readBits(const int* data, int index) {
  25. int dataIndexA = (index * BITS) >> DIVIDE_BITS;
  26. int dataIndexB = ((index + 1) * BITS) >> DIVIDE_BITS;
  27. int shifts = (index * BITS) & (INT_BITS - 1);
  28. if(dataIndexA == dataIndexB || ALIGNED) {
  29. return (data[dataIndexA] >> shifts) & MASK;
  30. }
  31. int bitsInA = INT_BITS - shifts;
  32. int r = (data[dataIndexA] >> shifts) & ((1 << bitsInA) - 1);
  33. r |= (data[dataIndexB] & ((1 << (BITS - bitsInA)) - 1)) << bitsInA;
  34. return r;
  35. }
  36. public:
  37. class BitInt {
  38. friend BitArray;
  39. int* data;
  40. int index;
  41. BitInt(int* data, int index) : data(data), index(index) {
  42. }
  43. BitInt(const BitInt& other) = default;
  44. BitInt(BitInt&& other) = default;
  45. public:
  46. BitInt& operator=(const BitInt& other) {
  47. return (*this) = static_cast<int> (other);
  48. }
  49. BitInt& operator=(BitInt&& other) {
  50. return (*this) = static_cast<int> (other);
  51. }
  52. BitInt& operator=(int i) {
  53. i &= MASK;
  54. int dataIndexA = (index * BITS) >> DIVIDE_BITS;
  55. int dataIndexB = ((index + 1) * BITS) >> DIVIDE_BITS;
  56. int shifts = (index * BITS) & (INT_BITS - 1);
  57. data[dataIndexA] &= ~(MASK << shifts);
  58. data[dataIndexA] |= (i << shifts);
  59. if(dataIndexA != dataIndexB && !ALIGNED) {
  60. int leftBits = BITS - (INT_BITS - shifts);
  61. int mask = (1 << leftBits) - 1;
  62. data[dataIndexB] &= ~mask;
  63. data[dataIndexB] |= (i >> (INT_BITS - shifts));
  64. }
  65. return *this;
  66. }
  67. operator int() const {
  68. return readBits(data, index);
  69. }
  70. };
  71. BitArray(int bits = 0) {
  72. fill(bits);
  73. }
  74. void fill(int bits) {
  75. for(int i = 0; i < N; i++) {
  76. (*this)[i] = bits;
  77. }
  78. }
  79. BitInt operator[](int index) {
  80. return BitInt(data, index);
  81. }
  82. int operator[](int index) const {
  83. return readBits(data, index);
  84. }
  85. constexpr int getLength() const {
  86. return N;
  87. }
  88. template<int L>
  89. void toString(StringBuffer<L>& s) const {
  90. s.append("[");
  91. for(int i = 0; i < N - 1; i++) {
  92. s.append((*this)[i]);
  93. s.append(", ");
  94. }
  95. if(N > 0) {
  96. s.append((*this)[N - 1]);
  97. }
  98. s.append("]");
  99. }
  100. };
  101. #endif