Bitset class implementation in C++

Bitset.cpp

#include <iostream>
#include <vector>
#include <limits>
#include <cmath>

using namespace std;

class Bitset {
    private:
        typedef unsigned long long int bitData; //Change this datatype if you want different subset sizes
        int dataSize = numeric_limits<bitData>::digits;
        bitData maxVal = numeric_limits<bitData>::max();
        bool defaultValue;
        int size;

        void IndexCheck(int index) {
            if(index >= size || index < 0) {
                cerr << "Warning: Index out of bounds. Index: " << index << ", Size: " << size << endl;
            }
        }

        void ShiftCheck(int& shift) {
            if(shift > size) {
                cerr << "Warning: Shift bigger than size. Shift: " << shift << ", Size: " << size << endl;
                shift = size;
            }
            if(shift < 0) {
                cerr << "Warning: Shift is negative. Shift: " << shift << ", Size: " << size << endl;
                shift = 0;
            }
        }
    public:
        vector<bitData> subsets;

        /*
            Constructor: Creates a bitset of a certain size and fills it with ones or zeros.
        */
        Bitset(int newSize, bool ones = false) {
            size = newSize;
            defaultValue = ones;
            subsets.assign(size / dataSize + 1, defaultValue * maxVal);
        }

        /*
            GetMask: Creates a mask of size dataSize that can be used to transform individual subsets.
        */
        bitData GetMask(int start, int end) {
            bitData mask;
            if(end == dataSize) {
                mask = 0;
            } else if (end == -1) {
                mask = 0;
            } else if(end == dataSize - 1) {
                mask = -1;
            } else {
                mask = ((bitData)1 << (end + 1)) - 1;
            }
            mask ^= ((bitData)1 << start) - 1;
            return mask;
        }

        /*
            DataSize: Returns the predefined size of each subset.
        */
        int DataSize() {
            return dataSize;
        }

        /*
            GetSize: Returns the total number of usable bits in the bitset.
        */
        int GetSize() {
            return size;
        }

        /*
            CountBits: Returns the number of set bits in the usable area.
        */
        int CountBits() {
            int bits = 0;
            for(int i = 0; i < subsets.size(); i++) {
                bitData tmp = subsets[i];
                if(i == subsets.size() - 1) {
                    bitData mask = GetMask(0, (size - 1) % dataSize);
                    tmp &= mask;
                }
                while(tmp != 0) {
                    tmp &= (tmp - 1);
                    bits++;
                }
            }
            return bits;
        }

        /*
            IsEmpty: Indicates whether all the bits are unset in the usable area.
        */
        bool IsEmpty() {
            int bits = CountBits();
            return bits == 0;
        }

        /*
            IsFull: Indicates whether all the bits are set in the usable area.
        */
        bool IsFull() {
            int bits = CountBits();
            return bits == size;
        }

        /*
            SetSize: Changes the amount of usable bits.
        */
        void SetSize(int newSize) {
            int currentSubset = ceil((float)size / dataSize);
            int endSubset = ceil((float)newSize / dataSize);
            if(currentSubset == endSubset) {
                size = newSize;
            } else {
                int oldSize = size;
                size = newSize;
                if(endSubset < currentSubset) {
                    for(int i = currentSubset; i > endSubset; i--) {
                        subsets.pop_back();
                    }
                } else {
                    for(int i = currentSubset; i < endSubset; i++) {
                        subsets.push_back(0);
                    }
                    Fill(oldSize, newSize - oldSize);
                }
            }
        }

        /*
            SetDefault: When the bitset changes size or is shifted, it will fill in new spaces with this default value.
        */
        void SetDefault(bool shiftValue) {
            defaultValue = shiftValue;
        }

        /*
            Copy: Creates a copy of the bitset.
        */
        Bitset Copy() {
            Bitset newBitset(size, defaultValue);
            newBitset.subsets = subsets;
            return newBitset;
        }

        /*
            GetSubset: Creates a new bitset containing only the bits from start to end.
        */
        Bitset GetSubset(int start, int end) {
            Bitset newBitset = Copy();
            newBitset.ShiftBack(start);
            newBitset.SetSize(end - start + 1);
            return newBitset;
        }

        /*
            ShiftBack: Shifts all bits by one space backwards.
        */
        void ShiftBack(int shift) {
            ShiftCheck(shift);
            int removeSubsets = shift / dataSize;
            for(int i = 0; i < removeSubsets; i++) {
                subsets.erase(subsets.begin());
            }
            bitData keepRange = GetMask(0, (shift - 1) % dataSize);
            for(int i = 0; i < subsets.size(); i++) {
                subsets[i] >>= (shift % dataSize);
                if(i != subsets.size() - 1) {
                    bitData nextBits = keepRange & subsets[i + 1];
                    nextBits <<= (dataSize - (shift % dataSize));
                    subsets[i] |= nextBits;
                }
            }
            for(int i = 0; i < removeSubsets; i++) {
                subsets.push_back(0);
            }
            Fill(size - shift, shift);
        }

        /*
            ShiftForward: Shifts all bits by one space forwards.
        */
        void ShiftForward(int shift) {
            ShiftCheck(shift);
            int removeSubsets = shift / dataSize;
            for(int i = 0; i < removeSubsets; i++) {
                subsets.pop_back();
            }
            bitData keepRange = GetMask(dataSize - (shift % dataSize), dataSize - 1);
            for(int i = subsets.size() - 1; i >= 0; i--) {
                subsets[i] <<= (shift % dataSize);
                if(i != 0) {
                    bitData nextBits = keepRange & subsets[i - 1];
                    nextBits >>= (dataSize - (shift % dataSize));
                    subsets[i] |= nextBits;
                }
            }
            for(int i = 0; i < removeSubsets; i++) {
                subsets.insert(subsets.begin(), 0);
            }
            Fill(0, shift);
        }

        /*
            Set: Sets a certain amount of values starting from index to one.
        */
        void Set(int index, int range = 1) {
            if(range <= 0) {
                return;
            }
            int start = index;
            int end = index + range - 1;
            IndexCheck(start);
            IndexCheck(end);
            int startSubset = start / dataSize;
            int endSubset = end / dataSize;
            bitData mask;
            if(startSubset == endSubset) {
                mask = GetMask(start % dataSize, end % dataSize);
                subsets[startSubset] |= mask;
            } else {
                for(int i = startSubset; i <= endSubset; i++) {
                    if(i == startSubset) {
                        mask = GetMask(start % dataSize, dataSize - 1);
                    } else if (i == endSubset) {
                        mask = GetMask(0, end % dataSize);
                    } else {
                        mask = GetMask(0, dataSize - 1);
                    }
                    subsets[i] |= mask;
                }
            }
        }

        /*
            Reset: Sets a certain amount of values starting from index to zero.
        */
        void Reset(int index, int range = 1) {
            if(range <= 0) {
                return;
            }
            int start = index;
            int end = index + range - 1;
            IndexCheck(start);
            IndexCheck(end);
            int startSubset = start / dataSize;
            int endSubset = end / dataSize;
            bitData mask;
            if(startSubset == endSubset) {
                mask = GetMask(start % dataSize, end % dataSize);
                subsets[startSubset] &= (~mask);
            } else {
                for(int i = startSubset; i <= endSubset; i++) {
                    if(i == startSubset) {
                        mask = GetMask(start % dataSize, dataSize - 1);
                    } else if (i == endSubset) {
                        mask = GetMask(0, end % dataSize);
                    } else {
                        mask = GetMask(0, dataSize - 1);
                    }
                    subsets[i] &= (~mask);
                }
            }
        }

        /*
            Toggle: Flips a certain amount of bits starting from index.
        */
        void Toggle(int index, int range = 1) {
            if(range <= 0) {
                return;
            }
            int start = index;
            int end = index + range - 1;
            IndexCheck(start);
            IndexCheck(end);
            int startSubset = start / dataSize;
            int endSubset = end / dataSize;
            bitData mask;
            if(startSubset == endSubset) {
                mask = GetMask(start % dataSize, end % dataSize);
                subsets[startSubset] ^= mask;
            } else {
                for(int i = startSubset; i <= endSubset; i++) {
                    if(i == startSubset) {
                        mask = GetMask(start % dataSize, dataSize - 1);
                    } else if (i == endSubset) {
                        mask = GetMask(0, end % dataSize);
                    } else {
                        mask = GetMask(0, dataSize - 1);
                    }
                    subsets[i] ^= mask;
                }
            }
        }

        /*
            Fill: Sets a certain amount of values starting from index to the default value.
        */
        void Fill(int index, int range = 1) {
            if(range <= 0) {
                return;
            }
            if(defaultValue) {
                Set(index, range);
            } else {
                Reset(index, range);
            }
        }

        /*
            Invert: Flips all of the bits in the subset.
        */
        void Invert() {
            for(int i = 0; i < subsets.size(); i++) {
                subsets[i] = ~subsets[i];
            }
        }

        /*
            Add: Performs the add operation with another bitset. If overflow is not set, the bitset will change in size.
        */
        void Add(Bitset bset, bool overflow) {
            SetDefault(0);
            Bitset addSet = bset.Copy();
            if(addSet.GetSize() < size) {
                addSet.SetDefault(0);
                addSet.SetSize(size);
            } else if (addSet.GetSize() > size) {
                if(!overflow) {
                    SetSize(addSet.GetSize());
                }
            }
            bool carry = false;
            bitData overflowCarryMask = ~GetMask(size % dataSize, size % dataSize);
            subsets[subsets.size() - 1] &= overflowCarryMask;
            for(int i = 0; i < subsets.size(); i++) {
                bitData carryMask = GetMask(dataSize - 1, dataSize - 1);
                bool nextCarry = ((subsets[i] & addSet.subsets[i]) & carryMask) != 0;
                subsets[i] += addSet.subsets[i] + carry;
                carry = nextCarry;
            }
            if(!overflow) {
                if(size % dataSize == 0) {
                    if(carry) {
                        SetSize(size + 1);
                        Set(size - 1);
                    }
                } else {
                    overflowCarryMask = ~overflowCarryMask;
                    if((subsets[subsets.size() - 1] & overflowCarryMask) != 0) {
                        SetSize(size + 1);
                    }
                }
            }
        }

        /*
            Subtract: Performs the subtraction operation with another bitset. If overflow is not set, the bitset will change in size.
        */
        void Subtract(Bitset bset, bool overflow) {
            SetDefault(0);
            Bitset remSet = bset.Copy();
            if(remSet.GetSize() < size) {
                remSet.SetDefault(0);
                remSet.SetSize(size);
            } else if (remSet.GetSize() > size) {
                if(!overflow) {
                    SetSize(remSet.GetSize());
                }
            }
            bool carry = false;
            bitData overflowCarryMask = ~GetMask(size % dataSize, size % dataSize);
            subsets[subsets.size() - 1] &= overflowCarryMask;
            for(int i = 0; i < subsets.size(); i++) {
                bitData carryMask = GetMask(dataSize - 1, dataSize - 1);
                bool nextCarry = ((subsets[i] & remSet.subsets[i]) & carryMask) != 0;
                subsets[i] -= remSet.subsets[i] - carry;
                carry = nextCarry;
            }
            if(!overflow) {
                if(size % dataSize == 0) {
                    if(carry) {
                        SetSize(size + 1);
                        Set(size - 1);
                    }
                } else {
                    overflowCarryMask = ~overflowCarryMask;
                    if((subsets[subsets.size() - 1] & overflowCarryMask) != 0) {
                        SetSize(size + 1);
                    }
                }
            }
        }

        /*
            AND: Performs the and operation with another bitset.
        */
        void AND(Bitset bset) {
            if(bset.GetSize() < size) {
                SetSize(bset.GetSize());
            }
            for(int i = 0; i < min(subsets.size(), bset.subsets.size()); i++) {
                subsets[i] &= bset.subsets[i];
            }
        }

        /*
            OR: Performs the or operation with another bitset.
        */
        void OR(Bitset bset) {
            if(bset.GetSize() < size) {
                SetSize(bset.GetSize());
            }
            for(int i = 0; i < min(subsets.size(), bset.subsets.size()); i++) {
                subsets[i] |= bset.subsets[i];
            }
        }

        /*
            XOR: Performs the xor operation with another bitset.
        */
        void XOR(Bitset bset) {
            if(bset.GetSize() < size) {
                SetSize(bset.GetSize());
            }
            for(int i = 0; i < min(subsets.size(), bset.subsets.size()); i++) {
                subsets[i] ^= bset.subsets[i];
            }
        }

        /*
            Test: Checks if the bit at index is set.
        */
        bool Test(int index) {
            IndexCheck(index);
            int subset = index / dataSize;
            bitData mask = (bitData)1 << (index % dataSize);
            return (subsets[subset] & mask) != 0;
        }

        /*
            Equals: Checks if two bitsets are equal.
        */
        bool Equals(Bitset bset) {
            if(bset.GetSize() != size) {
                return false;
            }
            bool equal = true;
            for(int i = 0; i < subsets.size(); i++) {
                bitData myData = subsets[i];
                bitData bsetData = bset.subsets[i];
                if(i == subsets.size() - 1) {
                    bitData mask = GetMask(0, (size - 1) % dataSize);
                    myData &= mask;
                    bsetData &= mask;
                }
                if(myData != bsetData) {
                    equal = false;
                    break;
                }
            }
            return equal;
        }

        /*
            Print: Prints a visual representation of the bitset from left to right.
        */
        void Print() {
            for(int i = 0; i < subsets.size(); i++) {
                for(int j = 0; j < dataSize; j++) {
                    if(i * dataSize + j >= size) {
                        break;
                    } else {
                        cout << Test(i * dataSize + j);
                    }
                }
                cout << endl;
            }
        }

        /*
            PrintValues: Prints each subset as a numerical value.
        */
        void PrintValues() {
            for(int i = 0; i < subsets.size(); i++) {
                bitData value = subsets[i];
                bitData mask = GetMask(0, (size - 1) % dataSize);
                if(i == subsets.size() - 1) {
                    value &= mask;
                }
                cout << "S" << i << ":\t" << value << endl;
            }
        }
};

int main() {
    //Bitset as bitwise values
    Bitset a(5);
    Bitset b(5);
    a.Set(1, 3);
    b.Set(1);
    b.Set(3, 2);
    cout << "A:\t ";
    a.Print();
    cout << "B:\t ";
    b.Print();
    a.XOR(b);
    cout << "A xor B: ";
    a.Print();
    cout << "Inverse: ";
    a.Invert();
    a.Print();
    cout << endl;
    //Bitset as a set of natural numbers
    Bitset mySet(1000);
    mySet.Set(1);
    mySet.Set(5);
    mySet.Set(12);
    mySet.Set(5);
    mySet.Set(13);
    cout << "Contains value 5?  " << mySet.Test(5) << endl;
    cout << "Contains value 6?  " << mySet.Test(6) << endl;
    cout << "Contains value 12? " << mySet.Test(12) << endl;
    cout << endl;
    //Bitset as binary representations of numbers
    Bitset n(8);
    Bitset m(8);
    for(int i = 0; i < 8; i++) {
        if(i % 2) {
            n.Set(i);
        }
        m.Set(i);
    }
    cout << "N:\t";
    n.Print();
    n.PrintValues();
    cout << "M:\t";
    m.Print();
    m.PrintValues();
    n.Add(m, false);
    cout << "N + M:  ";
    n.Print();
    n.PrintValues();
}