File indexing completed on 2024-04-06 12:22:14
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014 #ifndef BIT_ARRAY_H_
0015 #define BIT_ARRAY_H_
0016
0017
0018
0019
0020 #include <cassert>
0021 #include <iostream>
0022
0023
0024
0025
0026
0027 template <int N>
0028 class BitArray {
0029 public:
0030 class refToBit;
0031 friend class refToBit;
0032
0033
0034 class refToBit {
0035 friend class BitArray;
0036
0037
0038
0039 public:
0040 refToBit() {}
0041 refToBit(BitArray& b, int pos) {
0042 _word = &b.getWord(pos);
0043 _pos = getPosInWord(pos);
0044 }
0045 ~refToBit() {}
0046
0047 refToBit& operator=(const int val) {
0048 if (val) {
0049 *_word |= getPosMask(_pos);
0050 } else {
0051 *_word &= ~(getPosMask(_pos));
0052 }
0053 return *this;
0054 }
0055
0056 refToBit& operator=(const refToBit& rtb) {
0057 if ((*(rtb._word) & getPosMask(rtb._pos))) {
0058 *_word |= getPosMask(_pos);
0059 } else {
0060 *_word &= ~getPosMask(_pos);
0061 }
0062 return *this;
0063 }
0064
0065 int operator~() const { return ((*_word) & getPosMask(_pos)) == 0; }
0066
0067 operator int() const { return ((*_word) & getPosMask(_pos)) != 0; }
0068
0069 refToBit& flip() {
0070 *_word ^= getPosMask(_pos);
0071 return *this;
0072 }
0073
0074 private:
0075 unsigned* _word;
0076 int _pos;
0077 };
0078
0079 BitArray() { this->zero(); }
0080
0081 BitArray(const BitArray<N>& br) {
0082 for (int i = 0; i < this->nWords(); i++) {
0083 _data[i] = br._data[i];
0084 }
0085 this->cleanUnused();
0086 }
0087 BitArray(const char* str) {
0088 this->zero();
0089 this->assign(0, this->nBits(), str);
0090 this->cleanUnused();
0091 }
0092 BitArray(const char* str, const int p, const int n) {
0093 this->zero();
0094 this->assign(p, n, str);
0095 }
0096 BitArray(const unsigned i) {
0097 this->zero();
0098 _data[0] = i;
0099 this->cleanUnused();
0100 }
0101
0102
0103
0104
0105
0106
0107
0108
0109
0110
0111
0112
0113
0114
0115
0116
0117 inline int nBits() const { return N; }
0118 inline int size() const { return this->nBits(); }
0119
0120
0121 inline int nWords() const { return N / 32 + 1; }
0122
0123
0124 unsigned dataWord(const int i) const {
0125 assert(i >= 0 && i < this->nWords());
0126 return _data[i];
0127 }
0128 unsigned& dataWord(const int i) {
0129 assert(i >= 0 && i < this->nWords());
0130 return _data[i];
0131 }
0132
0133
0134 unsigned& getWord(const int pos) {
0135 assert(pos >= 0 && pos < this->nBits());
0136 return _data[pos / 32];
0137 }
0138 unsigned getWord(const int pos) const {
0139 assert(pos >= 0 && pos < this->nBits());
0140 return _data[pos / 32];
0141 }
0142
0143
0144 static int getPosInWord(const int pos) {
0145
0146 return pos % 32;
0147 }
0148
0149
0150 static unsigned getPosMask(const int pos) { return static_cast<unsigned>(1) << getPosInWord(pos); }
0151
0152
0153 int unusedBits() const {
0154 if (this->nBits() == 0)
0155 return 32;
0156 return 31 - ((this->nBits() - 1) % 32);
0157 }
0158
0159
0160 unsigned lastWordMask() const { return static_cast<unsigned>(0xffffffff) >> (this->unusedBits()); }
0161
0162
0163 void cleanUnused() { _data[this->nWords() - 1] &= (this->lastWordMask()); }
0164
0165
0166 int count() const {
0167 int n = 0;
0168 for (int i = 0; i < this->nBits(); i++) {
0169 if (this->element(i))
0170 n++;
0171 }
0172 return n;
0173 }
0174
0175
0176 int any() {
0177 int nw = this->nWords();
0178 int ub = unusedBits();
0179 if (this->dataWord(nw - 1) << ub != 0)
0180 return 1;
0181 if (nw > 1) {
0182 for (int iw = 0; iw < nw - 1; iw++) {
0183 if (this->dataWord(iw) != 0)
0184 return 1;
0185 }
0186 }
0187 return 0;
0188 }
0189
0190
0191 int none() {
0192 int nw = this->nWords();
0193 int ub = unusedBits();
0194 if (this->dataWord(nw - 1) << ub != 0xffffffff)
0195 return 1;
0196 if (nw > 1) {
0197 for (int iw = 0; iw < nw - 1; iw++) {
0198 if (this->dataWord(iw) != 0xffffffff)
0199 return 1;
0200 }
0201 }
0202 return 0;
0203 }
0204
0205
0206 int element(const int pos) const { return (getWord(pos) & getPosMask(pos)) != static_cast<unsigned>(0); }
0207 inline int test(const int i) const { return element(i); }
0208
0209
0210 void zero() {
0211 for (int i = 0; i < this->nWords(); i++) {
0212 _data[i] = 0x0;
0213 }
0214 }
0215 inline void reset() { zero(); }
0216
0217 void one() {
0218 for (int i = 0; i < this->nWords(); i++) {
0219 _data[i] = 0xffffffff;
0220 }
0221 }
0222
0223
0224 void set(const int i) { getWord(i) |= getPosMask(i); }
0225 void unset(const int i) { getWord(i) &= ~getPosMask(i); }
0226 inline void reset(const int i) { this->unset(i); }
0227
0228
0229 inline void set(const int i, const int val) { this->assign(i, 1, val); }
0230 inline void set(const int i, const char* str) { this->assign(i, 1, str); }
0231
0232
0233 void assign(const int p, const int n, const int val) {
0234 assert(p >= 0 && p + n <= this->nBits());
0235
0236 for (int i = 0; i < n; i++) {
0237 if (val >> i & 1) {
0238 this->set(p + i);
0239 } else {
0240 this->unset(p + i);
0241 }
0242 }
0243 }
0244 void assign(const int p, const int n, const BitArray<N>& val) {
0245 assert(p >= 0 && p + n <= this->nBits());
0246
0247 for (int i = 0; i < n; i++) {
0248 if (val.element(i)) {
0249 this->set(p + i);
0250 } else {
0251 this->unset(p + i);
0252 }
0253 }
0254 }
0255 void assign(const int p, const int n, const char* str) {
0256 assert(p >= 0 && p + n <= this->nBits());
0257
0258 for (int i = 0; i < n; i++) {
0259 assert(str[i] == '1' || str[i] == '0');
0260 if (str[i] == '1') {
0261 this->set(p + n - i - 1);
0262 } else {
0263 this->unset(p + n - i - 1);
0264 }
0265 }
0266 }
0267
0268
0269 unsigned read(const int p, const int n) const {
0270 assert(p >= 0 && p + n <= this->nBits());
0271 assert(n <= 32);
0272
0273 unsigned out = 0x0;
0274 for (int i = 0; i < n; i++) {
0275 if (this->test(p + i))
0276 out |= 1 << i;
0277 }
0278 return out;
0279 }
0280
0281
0282 BitArray<8> byte(const int i) const {
0283 BitArray<8> out;
0284 if (i >= 0 && i < 4 * this->nWords()) {
0285 unsigned k = (_data[i / 4] >> 8 * (i % 4)) & 0xff;
0286 out = k;
0287 }
0288 return out;
0289 }
0290
0291 BitArray<N>& operator=(const BitArray<N>& a) {
0292 if (this != &a) {
0293 for (int i = 0; i < this->nWords(); i++) {
0294 _data[i] = a._data[i];
0295 }
0296 }
0297 this->cleanUnused();
0298 return *this;
0299 }
0300
0301
0302 BitArray<N>& operator=(const unsigned i) {
0303 this->zero();
0304 _data[0] = i;
0305 this->cleanUnused();
0306 return *this;
0307 }
0308
0309
0310
0311
0312
0313
0314
0315
0316
0317
0318
0319
0320
0321
0322
0323 BitArray<N>& operator=(const char* str) {
0324 this->zero();
0325 for (int i = 0; i < this->nBits(); i++) {
0326 assert(str[i] == '1' || str[i] == '0');
0327 if (str[i] == '1') {
0328 this->set(this->nBits() - i - 1);
0329 } else if (str[i] == '0') {
0330 this->unset(this->nBits() - i - 1);
0331 } else {
0332 break;
0333 }
0334 }
0335 this->cleanUnused();
0336 return *this;
0337 }
0338
0339
0340 std::ostream& print(std::ostream& o = std::cout) const {
0341 for (int i = this->nBits() - 1; i >= 0; i--) {
0342 o << this->element(i);
0343 }
0344 return o;
0345 }
0346
0347
0348 refToBit operator[](const int pos) { return refToBit(*this, pos); }
0349 int operator[](const int pos) const { return element(pos); }
0350
0351
0352 bool operator==(const BitArray<N>& a) const {
0353 int nw = this->nWords();
0354 int ub = this->unusedBits();
0355 if (this->dataWord(nw - 1) << ub !=
0356 a.dataWord(nw - 1) << ub)
0357 return false;
0358 if (nw > 1) {
0359 for (int iw = 0; iw < nw - 1; iw++) {
0360 if (this->dataWord(iw) != a.dataWord(iw))
0361 return false;
0362 }
0363 }
0364 return true;
0365 }
0366
0367
0368 bool operator<(const BitArray<N>& a) const {
0369 int nw = this->nWords();
0370 int ub = this->unusedBits();
0371 unsigned aaa = this->dataWord(nw - 1) << ub;
0372 unsigned bbb = a.dataWord(nw - 1) << ub;
0373 if (aaa < bbb) {
0374 return true;
0375 } else if (aaa > bbb) {
0376 return false;
0377 }
0378 if (nw > 1) {
0379 for (int iw = nw - 2; iw >= 0; iw--) {
0380 if (this->dataWord(iw) < a.dataWord(iw)) {
0381 return true;
0382 } else if (this->dataWord(iw) > a.dataWord(iw)) {
0383 return false;
0384 }
0385 }
0386 }
0387 return false;
0388 }
0389
0390
0391 bool operator!=(const BitArray<N>& a) const { return !(a == *this); }
0392
0393
0394 bool operator>=(const BitArray<N>& a) const { return !(*this < a); }
0395
0396
0397 bool operator>(const BitArray<N>& a) const { return !(*this < a || *this == a); }
0398
0399
0400 bool operator<=(const BitArray<N>& a) const { return !(*this > a); }
0401
0402
0403 BitArray<N>& flip() {
0404 for (int i = 0; i < this->nWords(); i++) {
0405 _data[i] = ~_data[i];
0406 }
0407 return *this;
0408 }
0409
0410
0411 BitArray<N> operator~() const { return BitArray<N>(*this).flip(); }
0412
0413
0414 BitArray<N>& operator&=(const BitArray<N>& a) {
0415 for (int i = 0; i < this->nWords(); i++) {
0416 this->dataWord(i) &= a.dataWord(i);
0417 }
0418 return *this;
0419 }
0420
0421
0422 BitArray<N> operator&(const BitArray<N>& a) { return BitArray<N>(*this) &= a; }
0423
0424
0425 BitArray<N>& operator|=(const BitArray<N>& a) {
0426 for (int i = 0; i < this->nWords(); i++) {
0427 this->dataWord(i) |= a.dataWord(i);
0428 }
0429 return *this;
0430 }
0431
0432
0433 BitArray<N> operator|(const BitArray<N>& a) { return BitArray<N>(*this) |= a; }
0434
0435
0436 BitArray<N>& operator^=(const BitArray<N>& a) {
0437 for (int i = 0; i < this->nWords(); i++) {
0438 this->dataWord(i) ^= a.dataWord(i);
0439 }
0440 return *this;
0441 }
0442
0443
0444 BitArray<N> operator^(const BitArray<N>& a) { return BitArray<N>(*this) ^= a; }
0445
0446
0447 BitArray<N>& operator<<=(const int n) {
0448 assert(n >= 0 && n < this->nBits());
0449 if (n == 0)
0450 return *this;
0451 int i = 0;
0452 for (i = this->nBits() - 1; i >= n; i--)
0453 this->set(i, this->element(i - n));
0454 for (i = n - 1; i >= 0; i--)
0455 this->unset(i);
0456 return *this;
0457 }
0458
0459
0460 BitArray<N> operator<<(const int n) { return BitArray<N>(*this) <<= n; }
0461
0462
0463 BitArray<N>& operator>>=(const int n) {
0464 assert(n >= 0 && n < this->nBits());
0465 if (n == 0)
0466 return *this;
0467 int i = 0;
0468 for (i = 0; i < this->nBits() - n; i++)
0469 this->set(i, this->element(i + n));
0470 for (i = this->nBits() - n; i < this->nBits(); i++)
0471 this->unset(i);
0472 return *this;
0473 }
0474
0475
0476 BitArray<N> operator>>(const int n) { return BitArray<N>(*this) >>= n; }
0477
0478
0479 BitArray<N>& operator+=(const BitArray<N>& a) {
0480 int rep = 0;
0481 int sum = 0;
0482 for (int i = 0; i < this->nBits(); i++) {
0483 sum = this->element(i) ^ rep;
0484 rep = this->element(i) & rep;
0485 this->set(i, sum ^ a.element(i));
0486 rep |= (sum & a.element(i));
0487 }
0488 return *this;
0489 }
0490
0491
0492 BitArray<N> operator+(const BitArray<N>& a) { return BitArray<N>(*this) += a; }
0493
0494
0495 BitArray<N>& operator++(int) {
0496 int i = 0;
0497 while (i < this->nBits() && this->element(i) == 1) {
0498 this->unset(i);
0499 i++;
0500 }
0501 if (i < this->nBits())
0502 this->set(i);
0503 return *this;
0504 }
0505
0506
0507 BitArray<N> twoComplement() const { return BitArray<N>(~*this)++; }
0508
0509
0510 BitArray<N>& twoComplement() {
0511 (*this).flip();
0512 (*this)++;
0513 return *this;
0514 }
0515
0516
0517 BitArray<N>& operator-=(const BitArray<N>& a) { return *this += a.twoComplement(); }
0518
0519
0520 BitArray<N> operator-(const BitArray<N>& a) { return BitArray<N>(*this) -= a; }
0521
0522 private:
0523 unsigned _data[N / 32 + 1];
0524 };
0525
0526
0527
0528
0529
0530
0531
0532
0533 #endif