From 4984100559a00e055a502fc8fe85d7ca66589b36 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Tue, 7 Aug 2018 17:29:35 +0200 Subject: Clean up bit vector code --- chilbert/BigBitVec.hpp | 608 +++++++++++++++++++----------------------------- chilbert/FixBitVec.hpp | 331 +++++++++----------------- chilbert/Operations.hpp | 18 ++ 3 files changed, 367 insertions(+), 590 deletions(-) (limited to 'chilbert') diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp index 129f5d8..c5ade5d 100644 --- a/chilbert/BigBitVec.hpp +++ b/chilbert/BigBitVec.hpp @@ -19,574 +19,450 @@ #ifndef CHILBERT_BIGBITVEC_HPP #define CHILBERT_BIGBITVEC_HPP - #include "chilbert/FixBitVec.hpp" +#include #include #include #include -#define BBV_MIN(a,b) ((a)<(b)?(a):(b)) -#define BBV_MAX(a,b) ((a)>(b)?(a):(b)) -#define FBVS_NEEDED(b) ((BBV_MAX(b,1)+FBV_BITS-1)/FBV_BITS) -#define BBV_MODSPLIT(r,b,k) { b=(k); r=b/FBV_BITS; b-=r*FBV_BITS; } +#define FBVS_NEEDED(b) ((std::max(b, 1) + FBV_BITS - 1) / FBV_BITS) +#define BBV_MODSPLIT(r, b, k) \ + { \ + b = (k); \ + r = b / FBV_BITS; \ + b -= r * FBV_BITS; \ + } namespace chilbert { class CBigBitVec { public: - - // Constructor, with optional number of bits. - CBigBitVec( - int iBits = FBV_BITS - ) - : m_pcRacks{new FBV_UINT[iBits == 0 ? 0 : FBVS_NEEDED(iBits)]} - , m_iRacks{iBits == 0 ? 0 : FBVS_NEEDED(iBits)} + CBigBitVec(const int bits = 0) + : m_pcRacks{new FBV_UINT[bits == 0 ? 0 : FBVS_NEEDED(bits)]} + , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)} { } - - - // Copy construct. Creates duplicate. - CBigBitVec( - const CBigBitVec &cBBV - ) - : m_pcRacks{new FBV_UINT[cBBV.m_iRacks]} - , m_iRacks{cBBV.m_iRacks} + + CBigBitVec(const CBigBitVec& vec) + : m_pcRacks{new FBV_UINT[vec.m_iRacks]} + , m_iRacks{vec.m_iRacks} { - if (cBBV.m_pcRacks) { + if (vec.m_pcRacks) { memcpy(m_pcRacks.get(), - cBBV.m_pcRacks.get(), + vec.m_pcRacks.get(), sizeof(FBV_UINT) * m_iRacks); } } - // Move construct. - CBigBitVec( - CBigBitVec &&cBBV - ) = default; + CBigBitVec(CBigBitVec&& vec) = default; - // Copy constructor. - CBigBitVec( - const CFixBitVec &cFBV - ) - : m_pcRacks{new FBV_UINT[1]} - , m_iRacks{1} + CBigBitVec(const CFixBitVec& vec) + : m_pcRacks{new FBV_UINT[1]} + , m_iRacks{1} { - m_pcRacks[0] = cFBV.rack(); + m_pcRacks[0] = vec.rack(); } + /// Return the size in bits + int size() const { return m_iRacks * FBV_BITS; } - // Returns the current size in bits. - int - size() const + /// Set all bits to zero + CBigBitVec& reset() { - return m_iRacks*FBV_BITS; - } - - - // zeros the bit-vector. - CBigBitVec & - reset() - { - memset(m_pcRacks.get(), 0, sizeof(CFixBitVec) * m_iRacks); - - return (*this); + return *this; } - - // truncates the bit-vector to a given precision in - // bits (zeroes MSBs without shrinking the vector) - CBigBitVec & - truncate( - int iBits - ) + /// Truncate to a given precision in bits (zero MSBs) + CBigBitVec& truncate(const int bits) { - assert( iBits >= 0 && iBits <= size() ); - int r, b, i; + assert(bits >= 0 && bits <= size()); + int r, b; + + BBV_MODSPLIT(r, b, bits); - BBV_MODSPLIT(r,b,iBits); - - if ( r >= m_iRacks ) - return (*this); + if (r >= m_iRacks) { + return *this; + } // Truncate rack that contains the split point - m_pcRacks[r] &= FBVN1S(iBits); - - for ( i = r+1; i < m_iRacks; i++ ) + m_pcRacks[r] &= FBVN1S(bits); + + for (int i = r + 1; i < m_iRacks; ++i) { m_pcRacks[i] = 0; + } - return (*this); + return *this; } - - // Assignment operator. No resizing. - CBigBitVec & - operator=( - const CBigBitVec &cBBV - ) + /// Non-resizing assignment + CBigBitVec& operator=(const CBigBitVec& vec) { - if ( m_iRacks < cBBV.m_iRacks ) - { - memcpy(m_pcRacks.get(), cBBV.m_pcRacks.get(), sizeof(CFixBitVec) * m_iRacks); + if (m_iRacks < vec.m_iRacks) { + memcpy(m_pcRacks.get(), + vec.m_pcRacks.get(), + sizeof(CFixBitVec) * m_iRacks); } else { if (m_pcRacks) { - if (cBBV.m_pcRacks) { + if (vec.m_pcRacks) { memcpy(m_pcRacks.get(), - cBBV.m_pcRacks.get(), - sizeof(CFixBitVec) * cBBV.m_iRacks); + vec.m_pcRacks.get(), + sizeof(CFixBitVec) * vec.m_iRacks); } - memset(m_pcRacks.get() + cBBV.m_iRacks, + memset(m_pcRacks.get() + vec.m_iRacks, 0, - sizeof(CFixBitVec) * (m_iRacks - cBBV.m_iRacks)); + sizeof(CFixBitVec) * (m_iRacks - vec.m_iRacks)); } } - return (*this); + return *this; } - CBigBitVec & - operator=( - CBigBitVec &&cBBV - ) = default; - CBigBitVec & - operator=( - const CFixBitVec &cFBV - ) + CBigBitVec& operator=(CBigBitVec&& vec) = default; + + CBigBitVec& operator=(const CFixBitVec& vec) { - m_pcRacks[0] = cFBV.rack(); + m_pcRacks[0] = vec.rack(); memset(m_pcRacks.get() + 1, 0, sizeof(FBV_UINT) * (m_iRacks - 1)); - return (*this); + return *this; } - CBigBitVec & - operator=( - FBV_UINT j - ) + + CBigBitVec& operator=(const FBV_UINT j) { m_pcRacks[0] = j; memset(m_pcRacks.get() + 1, 0, sizeof(CFixBitVec) * (m_iRacks - 1)); - return (*this); + return *this; } - // Returns the value of the nth bit. - bool - test( - int iIndex - ) const + /// Return the value of the `index`th bit + bool test(const int index) const { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); + BBV_MODSPLIT(r, b, index); return testBit(m_pcRacks[r], b); } - - // Sets the value of the nth bit. - CBigBitVec & - set( - int iIndex, - bool bBit = true - ) + /// Set the `index`th bit to 1 + CBigBitVec& set(const int index) { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); - setBit(m_pcRacks[r], b, bBit); - return (*this); + BBV_MODSPLIT(r, b, index); + setBit(m_pcRacks[r], b); + return *this; } - - // Toggles the value of the nth bit. - CBigBitVec & - toggle( - int iIndex - ) + /// Reset the `index`th bit to 0 + CBigBitVec& reset(const int index) { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); - m_pcRacks[r] ^= (FBV1<= 0 && index < size()); + int r, b; + BBV_MODSPLIT(r, b, index); + setBit(m_pcRacks[r], b, value); + return *this; + } - // In place AND. - CBigBitVec & - operator&=( - const CBigBitVec &cBBV - ) + /// Toggle the value of the `index`th bit + CBigBitVec& toggle(const int index) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] &= cBBV.m_pcRacks[i]; - - return (*this); + assert(index >= 0 && index < size()); + int r, b; + BBV_MODSPLIT(r, b, index); + m_pcRacks[r] ^= (FBV1 << index); + return *this; } + CBigBitVec& operator&=(const CBigBitVec& vec) + { + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] &= vec.m_pcRacks[i]; + } - // AND operator. - CBigBitVec - operator&( - const CBigBitVec &cBBV - ) const + return *this; + } + + CBigBitVec operator&(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t &= cBBV; + CBigBitVec t(*this); + t &= vec; return t; } - - // In place OR. - CBigBitVec & - operator|=( - const CBigBitVec &cBBV - ) + CBigBitVec& operator|=(const CBigBitVec& vec) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] |= cBBV.m_pcRacks[i]; - - return (*this); - } + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] |= vec.m_pcRacks[i]; + } + return *this; + } - // OR operator. - CBigBitVec - operator|( - const CBigBitVec &cBBV - ) const + CBigBitVec operator|(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t |= cBBV; + CBigBitVec t(*this); + t |= vec; return t; } - - // In place XOR. - CBigBitVec & - operator^=( - const CBigBitVec &cBBV - ) + CBigBitVec& operator^=(const CBigBitVec& vec) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] ^= cBBV.m_pcRacks[i]; - - return (*this); - } + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] ^= vec.m_pcRacks[i]; + } + return *this; + } - // XOR operator. - CBigBitVec - operator^( - const CBigBitVec &cBBV - ) const + CBigBitVec operator^(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t ^= cBBV; + CBigBitVec t(*this); + t ^= vec; return t; } - - // Shift left operation, in place. - CBigBitVec & - operator<<=( - int iBits - ) + CBigBitVec& operator<<=(const int bits) { - assert( iBits >= 0 ); + assert(bits >= 0); int r, b, i; // No shift? - if ( iBits == 0 ) - return (*this); + if (bits == 0) { + return *this; + } - BBV_MODSPLIT(r,b,iBits); + BBV_MODSPLIT(r, b, bits); // All racks? - if ( r >= m_iRacks ) - { + if (r >= m_iRacks) { reset(); - return (*this); + return *this; } // Do rack shifts. - if ( r > 0 ) - { - for ( i = m_iRacks-1; i >= r; i-- ) - m_pcRacks[i] = m_pcRacks[i-r]; - for ( ; i >= 0; i-- ) + if (r > 0) { + for (i = m_iRacks - 1; i >= r; --i) { + m_pcRacks[i] = m_pcRacks[i - r]; + } + for (; i >= 0; --i) { m_pcRacks[i] = 0; + } } // Do bit shifts. - if ( b > 0 ) - { + if (b > 0) { int bi = FBV_BITS - b; - for ( i = m_iRacks-1; i >= r+1; i-- ) - { + for (i = m_iRacks - 1; i >= r + 1; --i) { m_pcRacks[i] <<= b; - m_pcRacks[i] |= m_pcRacks[i-1] >> bi; + m_pcRacks[i] |= m_pcRacks[i - 1] >> bi; } m_pcRacks[i] <<= b; } - return (*this); + return *this; } - - // Shift left operation. - CBigBitVec - operator<<( - int iBits - ) const + CBigBitVec operator<<(const int bits) const { - CBigBitVec t( *this ); - t <<= iBits; + CBigBitVec t(*this); + t <<= bits; return t; } - - // Shift right operation, in place. - CBigBitVec & - operator>>=( - int iBits - ) + CBigBitVec& operator>>=(const int bits) { - assert( iBits >= 0 ); + assert(bits >= 0); int r, b, i; // No shift? - if ( iBits == 0 ) - return (*this); + if (bits == 0) { + return *this; + } - BBV_MODSPLIT(r,b,iBits); + BBV_MODSPLIT(r, b, bits); // All racks? - if ( r >= m_iRacks ) - { + if (r >= m_iRacks) { reset(); - return (*this); + return *this; } // Do rack shifts. - if ( r > 0 ) - { - for ( i = 0; i < m_iRacks-r; i++ ) - m_pcRacks[i] = m_pcRacks[i+r]; - for ( ; i < m_iRacks; i++ ) + if (r > 0) { + for (i = 0; i < m_iRacks - r; ++i) { + m_pcRacks[i] = m_pcRacks[i + r]; + } + for (; i < m_iRacks; ++i) { m_pcRacks[i] = 0; + } } // Do bit shifts. - if ( b > 0 ) - { + if (b > 0) { int bi = FBV_BITS - b; - for ( i = 0; i < m_iRacks-r-1; i++ ) - { + for (i = 0; i < m_iRacks - r - 1; ++i) { m_pcRacks[i] >>= b; - m_pcRacks[i] |= m_pcRacks[i+1] << bi; + m_pcRacks[i] |= m_pcRacks[i + 1] << bi; } m_pcRacks[i] >>= b; } - return (*this); + return *this; } - - // Shift right operation. - CBigBitVec - operator>>( - int iBits - ) const + CBigBitVec operator>>(const int bits) const { - CBigBitVec t( *this ); - t >>= iBits; + CBigBitVec t(*this); + t >>= bits; return t; } - - // Right rotation, in place. - CBigBitVec & - rotr( - int iBits, - int iWidth - ) + /// Right-rotate the least significant `width` bits by `bits` positions + CBigBitVec& rotr(const int bits, int width) { - assert( iBits >= 0 ); + assert(bits >= 0); // Fill in the width, if necessary. - if ( iWidth <= 0 ) - iWidth = size(); + if (width <= 0) { + width = size(); + } // Modulo the number of bits. - assert( iBits < iWidth ); - if ( iBits == 0 ) return (*this); + assert(bits < width); + if (bits == 0) { + return *this; + } // Ensure we are truncated appropriately. - truncate(iWidth); + truncate(width); - CBigBitVec t1( *this ); - (*this) >>= iBits; - t1 <<= (iWidth-iBits); + CBigBitVec t1(*this); + (*this) >>= bits; + t1 <<= (width - bits); (*this) |= t1; - - truncate(iWidth); - return (*this); - } + truncate(width); + return *this; + } - // Left rotation, in place. - CBigBitVec & - rotl( - int iBits, - int iWidth - ) + /// Left-rotate the least significant `width` bits by `bits` positions + CBigBitVec& rotl(const int bits, int width) { - assert( iBits >= 0 ); + assert(bits >= 0); // Fill in the width, if necessary. - if ( iWidth <= 0 ) - iWidth = size(); + if (width <= 0) { + width = size(); + } // Modulo the number of bits. - assert( iBits < iWidth ); - if ( iBits == 0 ) return (*this); + assert(bits < width); + if (bits == 0) { + return *this; + } // Ensure we are truncated appropriately. - truncate(iWidth); + truncate(width); - CBigBitVec t1( *this ); - (*this) <<= iBits; - t1 >>= (iWidth-iBits); + CBigBitVec t1(*this); + (*this) <<= bits; + t1 >>= (width - bits); (*this) |= t1; - truncate(iWidth); + truncate(width); - return (*this); + return *this; } - - // Returns true if the rack is zero valued. - bool - none() const + /// Return true iff all bits are zero + bool none() const { - int i; - for ( i = 0; i < m_iRacks; i++ ) - if ( m_pcRacks[i] ) return false; + for (int i = 0; i < m_iRacks; ++i) { + if (m_pcRacks[i]) { + return false; + } + } return true; } - - // Returns the index of the first set bit. - // (numbered 1 to n, with 0 meaning no bits were set) - int - fsb() const + /// Return 1 + the index of the first set bit, or 0 if there are none + int fsb() const { - for (int i = 0; i < m_iRacks; ++i ) - { + for (int i = 0; i < m_iRacks; ++i) { const int j = ffs(m_pcRacks[i]); - if ( j ) { + if (j) { return (i * FBV_BITS) + j; } } return 0; } - - // Complement - CBigBitVec & - flip() + /// Flip all bits (one's complement) + CBigBitVec& flip() { - int i; - for ( i = 0; i < m_iRacks; i++ ) + for (int i = 0; i < m_iRacks; ++i) { m_pcRacks[i] = ~m_pcRacks[i]; - return (*this); - } - - - // Returns the first rack. - FBV_UINT & - rack() - { - return m_pcRacks[0]; - } - FBV_UINT - rack() const - { - return m_pcRacks[0]; + } + return *this; } + /// Return the first rack + FBV_UINT& rack() { return m_pcRacks[0]; } + FBV_UINT rack() const { return m_pcRacks[0]; } - // Returns the racks. - FBV_UINT * - racks() - { - return m_pcRacks.get(); - } - const FBV_UINT * - racks() const - { - return m_pcRacks.get(); - } - + /// Return a pointer to the racks + FBV_UINT* racks() { return m_pcRacks.get(); } + const FBV_UINT* racks() const { return m_pcRacks.get(); } - // Returns the number of racks. - int - rackCount() const - { - return m_iRacks; - } + /// Return the number of racks + int rackCount() const { return m_iRacks; } - private: - friend void grayCode(CBigBitVec&); - friend void grayCodeInv(CBigBitVec&); - // Right rotates entire racks (in place). - void - rackRotr( - int k - ) + void rackRotr(int k) { - assert( 0 <= k && k < m_iRacks ); - - int c, v; - FBV_UINT tmp; - - if (k == 0) return; - - c = 0; - for (v = 0; c < m_iRacks; v++) - { - int t = v, tp = v + k; - tmp = m_pcRacks[v]; + assert(0 <= k && k < m_iRacks); + + if (k == 0) { + return; + } + + int c = 0; + for (int v = 0; c < m_iRacks; ++v) { + int t = v, tp = v + k; + const int tmp = m_pcRacks[v]; c++; - while (tp != v) - { + while (tp != v) { m_pcRacks[t] = m_pcRacks[tp]; - t = tp; + t = tp; tp += k; - if (tp >= m_iRacks) tp -= m_iRacks; + if (tp >= m_iRacks) { + tp -= m_iRacks; + } c++; } m_pcRacks[t] = tmp; } - - return; } - std::unique_ptr m_pcRacks; - int m_iRacks; + int m_iRacks; }; template <> @@ -595,10 +471,10 @@ grayCode(CBigBitVec& value) { FBV_UINT s = 0; - for (int i = value.rackCount() - 1; i >= 0; i--) { + for (int i = value.rackCount() - 1; i >= 0; --i) { const FBV_UINT t = value.racks()[i] & 1; - grayCode(value.m_pcRacks[i]); - value.m_pcRacks[i] ^= (s << (FBV_BITS - 1)); + grayCode(value.racks()[i]); + value.racks()[i] ^= (s << (FBV_BITS - 1)); s = t; } } @@ -610,7 +486,7 @@ grayCodeInv(CBigBitVec& value) FBV_UINT s = 0; for (int i = value.rackCount() - 1; i >= 0; --i) { - FBV_UINT& rack = value.m_pcRacks[i]; + FBV_UINT& rack = value.racks()[i]; grayCodeInv(rack); if (s) { rack = ~rack; diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp index d8fee9a..bec5ba1 100644 --- a/chilbert/FixBitVec.hpp +++ b/chilbert/FixBitVec.hpp @@ -26,316 +26,199 @@ namespace chilbert { -// This must be an unsigned integer that is either -// 32 or 64 bits. Otherwise, there are places in the -// code that simply will not work. -// For speed, this should be the native word size. +/* This must be an unsigned integer that is either 32 or 64 bits. Otherwise, + there are places in the code that simply will not work. For speed, this + should be the native word size. */ typedef uint64_t FBV_UINT; -#define FBV_BITS 64 -#define FBV0 ((FBV_UINT)0) -#define FBV1 ((FBV_UINT)1) -#define FBV1S (~FBV0) -#define FBVN1S(n) (n==FBV_BITS?FBV1S:(FBV1< 0); } - // Assignment operator. - CFixBitVec & - operator=( - const CFixBitVec &cFBV - ) + /// Set the `index`th bit to 1 + CFixBitVec& set(const int index) { - m_uiRack = cFBV.m_uiRack; - return (*this); + assert(0 <= index && index < FBV_BITS); + m_rack |= ((FBV_UINT)1 << index); + return *this; } - // Assignment operator. - CFixBitVec & - operator=( - FBV_UINT i - ) + /// Reset the `index`th bit to 0 + CFixBitVec& reset(const int index) { - m_uiRack = i; - return (*this); + assert(0 <= index && index < FBV_BITS); + m_rack &= ~((FBV_UINT)1 << index); + return *this; } - // Returns the value of the nth bit. - bool - test( - int iIndex - ) const + /// Set the `index`th bit to `value` + CFixBitVec& set(const int index, const bool value) { - assert( 0 <= iIndex && iIndex < FBV_BITS ); - return ( (m_uiRack & (FBV1< 0 ); + assert(0 <= index && index < FBV_BITS); + m_rack ^= (-value ^ m_rack) & ((FBV_UINT)1 << index); + return *this; } - // Sets the value of the nth bit. - CFixBitVec & - set( - int iIndex, - bool bBit = true - ) + /// Toggle the value of the `index`th bit + CFixBitVec& toggle(const int index) { - assert( 0 <= iIndex && iIndex < FBV_BITS ); - FBV_UINT m = (FBV1<>=( - int iBits - ) + CFixBitVec& operator>>=(const int bits) { - m_uiRack >>= iBits; - return (*this); + m_rack >>= bits; + return *this; } - // Shift right operation. - CFixBitVec - operator>>( - int iBits - ) const + CFixBitVec operator>>(const int bits) const { CFixBitVec t(*this); - t >>= iBits; + t >>= bits; return t; } - // Right rotation, in place. - CFixBitVec & - rotr( - int iBits, - int iWidth - ) - { - assert( iBits >= 0 ); - assert( iWidth > 0 ); - assert( iBits < iWidth ); - m_uiRack &= FBVN1S(iWidth); - m_uiRack = (m_uiRack>>iBits) | (m_uiRack<<(iWidth-iBits)); - m_uiRack &= FBVN1S(iWidth); - return (*this); - } - - // Left rotation, in place. - CFixBitVec & - rotl( - int iBits, - int iWidth - ) + /// Right-rotate the least significant `width` bits by `bits` positions + CFixBitVec& rotr(const int bits, const int width) { - assert( iBits >= 0 ); - assert( iWidth > 0 ); - assert( iBits < iWidth ); - m_uiRack &= FBVN1S(iWidth); - m_uiRack = (m_uiRack<>(iWidth-iBits)); - m_uiRack &= FBVN1S(iWidth); - return (*this); + assert(bits >= 0); + assert(width > 0); + assert(bits < width); + m_rack &= FBVN1S(width); + m_rack = (m_rack >> bits) | (m_rack << (width - bits)); + m_rack &= FBVN1S(width); + return *this; } - // Is the bit rack zero valued? - bool - none() const + /// Left-rotate the least significant `width` bits by `bits` positions + CFixBitVec& rotl(int bits, int width) { - return m_uiRack == 0; + assert(bits >= 0); + assert(width > 0); + assert(bits < width); + m_rack &= FBVN1S(width); + m_rack = (m_rack << bits) | (m_rack >> (width - bits)); + m_rack &= FBVN1S(width); + return *this; } - // Returns the index of the first set bit, numbered from - // 1 to n. 0 means there were no set bits. - int - fsb() const - { - return chilbert::ffs(m_uiRack); - } + /// Return true iff all bits are zero + bool none() const { return m_rack == 0; } + /// Return 1 + the index of the first set bit, or 0 if there are none + int fsb() const { return chilbert::ffs(m_rack); } - // Ones-complements the rack - CFixBitVec & - flip() + /// Flip all bits (one's complement) + CFixBitVec& flip() { - m_uiRack = ~m_uiRack; - return (*this); + m_rack = ~m_rack; + return *this; } - // Returns the first rack. - FBV_UINT & - rack() - { - return m_uiRack; - } - FBV_UINT - rack() const - { - return m_uiRack; - } + /// Return the first rack + FBV_UINT& rack() { return m_rack; } + FBV_UINT rack() const { return m_rack; } - // Return a pointer to the racks - FBV_UINT * - racks() - { - return &m_uiRack; - } - const FBV_UINT * - racks() const - { - return &m_uiRack; - } + /// Return a pointer to the racks + FBV_UINT* racks() { return &m_rack; } + const FBV_UINT* racks() const { return &m_rack; } - // Returns the number of racks. - int - rackCount() - { - return 1; - } + /// Return the number of racks + int rackCount() { return 1; } private: - static_assert( 8*sizeof(FBV_UINT) == FBV_BITS, "" ); - static_assert( (sizeof(FBV_UINT) == 4) || (sizeof(FBV_UINT) == 8), "" ); + static_assert(8 * sizeof(FBV_UINT) == FBV_BITS, ""); + static_assert((sizeof(FBV_UINT) == 4) || (sizeof(FBV_UINT) == 8), ""); - FBV_UINT m_uiRack; + FBV_UINT m_rack{}; }; template <> diff --git a/chilbert/Operations.hpp b/chilbert/Operations.hpp index 578daaf..06a06fa 100644 --- a/chilbert/Operations.hpp +++ b/chilbert/Operations.hpp @@ -52,6 +52,16 @@ testBit(const T& field, const BitsetIndex index) return field.test(index); } +/// Set the `index`th bit in `field` +template +void +setBit(T& field, const IntegralIndex index) +{ + assert(size_t(index) < sizeof(field) * CHAR_BIT); + field |= ((T)1 << index); + assert(testBit(field, index)); +} + /// Set the `index`th bit in `field` to `value` template void @@ -62,6 +72,14 @@ setBit(T& field, const IntegralIndex index, const bool value) assert(testBit(field, index) == value); } +/// Set the `index`th bit in `field` +template +void +setBit(T& field, const BitsetIndex index) +{ + field.set(index); +} + /// Set the `index`th bit in `field` to `value` template void -- cgit v1.2.1