bitset.hpp

Go to the documentation of this file.

/*
 
Copyright 2025 Matthew Tolman
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
   http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
*/
 
#pragma once
 
#ifndef MTCORE_BITSET_HPP
#define MTCORE_BITSET_HPP
 
#include <limits>
 
#include "optional.hpp"
#include "result.hpp"
#include "slice.hpp"
 
namespace mtcore {
  enum class BitStrInitError {
    ALLOCATION_FAILED = static_cast<int>(AllocationError::ALLOCATION_FAILED),
    INVALID_BINARY_STRING
  };

  struct Bitset {
    Slice<u64> bits;
    size_t len = 0;

    [[nodiscard]] Result<void, AllocationError> init(mtcore::Allocator &allocator, const size_t total) {
      ensure(!bits.head, "ALREADY ALLOCATED");
      this->len           = total;
      const auto sliceLen = total / 64 + (total % 64 ? 1 : 0);
      ensure(sliceLen > 0, "CANNOT CREATE EMPTY BITSET");
 
      const auto allocBitsRes = allocator.create_many<u64>(sliceLen);
      if (allocBitsRes.is_error()) {
        return allocBitsRes.error();
      }
      bits = *allocBitsRes;
      memset(bits.head, 0, sliceLen * sizeof(u64));
      return success();
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const Slice<const char> binaryStr) {
      ensure(!bits.head, "ALREADY ALLOCATED");
      return init(allocator, binaryStr.len, binaryStr);
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const size_t total,
                                       const Slice<const char> binaryStr) {
      ensure(!bits.head, "ALREADY ALLOCATED");
      {
        char cur  = '\0';
        auto iter = binaryStr.iter();
        while (iter.next().copy_if_present(cur)) {
          if (cur != '1' && cur != '0') {
            return error(BitStrInitError::INVALID_BINARY_STRING);
          }
        }
      }
 
      auto initRes = init(allocator, total);
      if (initRes.is_error()) {
        return error(BitStrInitError::ALLOCATION_FAILED);
      }
 
      char cur     = '\0';
      auto iter    = binaryStr.iter();
      size_t index = 0;
      while (iter.next().copy_if_present(cur)) {
        mtdefer { ++index; };
        if (cur == '1') {
          set(index, true);
        }
      }
      return success();
    }

    void deinit(mtcore::Allocator &allocator) {
      if (bits.head != nullptr) {
        allocator.destroy_many(bits);
      }
      len = 0;
    }

    struct BitsetAccess {
      size_t pos;
      Bitset &bs;
 
      [[nodiscard]] operator bool() const { return bs.at(pos); }
      [[nodiscard]] bool val() const { return bs.at(pos); }
      BitsetAccess &set(const bool newVal) {
        bs.set(pos, newVal);
        return *this;
      }
 
      BitsetAccess &operator=(const bool val) { return set(val); }
      BitsetAccess &operator&=(const bool other) { return set(val() & other); }
      BitsetAccess &operator|=(const bool other) { return set(val() | other); }
      BitsetAccess &operator^=(const bool other) { return set(val() ^ other); }
    };

    [[nodiscard]] BitsetAccess operator[](const size_t index) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      return {.pos = index, .bs = *this};
    }

    [[nodiscard]] bool operator[](const size_t index) const { return at(index); }

    [[nodiscard]] size_t size() const { return len; }

    [[nodiscard]] bool at(const size_t pos) const {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "OUT OF BOUNDS ACCESS");
      const auto block  = pos / 64;
      const auto bit    = pos % 64;
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      return (bits[block] & bitMask) != 0;
    }

    Result<Bitset, AllocationError> clone(mtcore::Allocator &allocator) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      return clone(allocator, len);
    }

    Result<Bitset, AllocationError> clone(mtcore::Allocator &allocator, const size_t newLen) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      Bitset res;
      auto initRes = res.init(allocator, newLen);
      if (initRes.is_error()) {
        return initRes.error();
      }
      for (size_t i = 0; i < res.bits.len && i < bits.len; ++i) {
        res.bits[i] = bits[i];
      }
      return res;
    }
 
    Result<void, AllocationError> resize(Allocator &alloc, const size_t newLen, const bool newVal = false) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      Bitset res;
      auto initRes = res.init(alloc, newLen);
 
      if (initRes.is_error()) {
        return initRes.error();
      }
 
      // by setting all, any new chunks will have the new value set
      if (newVal) {
        res.set_all(true);
      }
 
      // Copy the old bits over, this will overwrite any existing set bits
      for (size_t i = 0; i < res.bits.len && i < bits.len; ++i) {
        res.bits[i] = bits[i];
      }
 
      if (newVal) {
        // For the last segment copied over, just set the new bits individually
        for (size_t i = (bits.len - 1) * 64; i < newLen && i < bits.len * 64; ++i) {
          set(i, true);
        }
      }
 
      // Now that we have our copy, do a swap
      std::swap(bits, res.bits);
      std::swap(len, res.len);
 
      // Finally, clean up the old bits
      res.deinit(alloc);
      return success();
    }

    Bitset &set(const size_t pos, const bool val) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "OUT OF BOUNDS ACCESS");
      const u64 block = pos / 64;
      const u64 bit   = pos % 64;
      ensure(bit + block * 64 == pos, 'BAD POSITION DECONSTRUCT');
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      if (val) {
        bits[block] |= bitMask;
      }
      else {
        bits[block] &= ~bitMask;
      }
      return *this;
    }

    Bitset &toggle(const size_t pos) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "OUT OF BOUNDS ACCESS");
      const u64 block   = pos / 64;
      const u64 bit     = pos % 64;
      const u64 bitMask = 0x1 << bit;
      bits[block] ^= bitMask;
      return *this;
    }

    [[nodiscard]] Optional<size_t> first_set() const {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < bits.len; ++i) {
        if (bits[i]) {
          return 64 * i + std::countr_zero(bits[i]);
        }
      }
      return nullopt;
    }

    [[nodiscard]] size_t pop_count() const {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      size_t count = 0;
      for (size_t i = 0; i < bits.len; ++i) {
        count += std::popcount(bits[i]);
      }
      return count;
    }

    struct SetBitIter {
      const Bitset &bs;
      u64 curMask;
      size_t curIndex;

      Optional<size_t> next() {
        while (!curMask && ++curIndex < bs.bits.len) {
          curMask = bs.bits[curIndex];
        }
        if (curIndex >= bs.bits.len) {
          return nullopt;
        }
        mtdefer { curMask ^= static_cast<u64>(0x1) << std::countr_zero(curMask); };
        const size_t res = 64 * curIndex + std::countr_zero(curMask);
        return res;
      }
    };

    [[nodiscard]] SetBitIter set_bits() const {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      return SetBitIter{*this, bits[0], 0};
    }
 
    Bitset &operator&=(const Bitset &other) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      size_t i = 0;
      for (; i < other.bits.len && i < bits.len; ++i) {
        bits[i] &= other.bits[i];
      }
      for (; i < bits.len; ++i) {
        bits[i] = 0;
      }
      return *this;
    }
 
    Bitset &operator|=(const Bitset &other) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] |= other.bits[i];
      }
      return *this;
    }
 
    Bitset &operator^=(const Bitset &other) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] ^= other.bits[i];
      }
      return *this;
    }

    void set_all(const bool value) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      const u64 mask = value ? std::numeric_limits<u64>::max() : 0;
 
      // For the first n 64-bit segments, just set them all
      for (size_t i = 0; i < bits.len - 1; ++i) {
        bits[i] = mask;
      }
 
      // For the last segment, just set what we have allocated
      for (size_t i = (bits.len - 1) * 64; i < size(); ++i) {
        set(i, value);
      }
    }
 
    Bitset &operator<<=(const size_t amount) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = bits.len - i - 1;
          const auto sourceIndex = bits.len - i - 1 - blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = 0; i < blockShift; ++i) {
          bits[i] = 0;
        }
 
        constexpr u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask >> bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) >> (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) << bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask >> (len % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }
 
    Bitset &operator>>=(const size_t amount) {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = i;
          const auto sourceIndex = i + blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = bits.len - blockShift; i < bits.len; ++i) {
          bits[i] = 0;
        }
 
        const u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask << bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) << (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) >> bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask << (len % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }
  };

  struct Bitset2D {
    Bitset underlying;
    size_t width;
    size_t height;

    Result<void, AllocationError> init(mtcore::Allocator &allocator, const size_t height, const size_t width) {
      ensure(width, "INVALID WIDTH");
      ensure(height, "INVALID HEIGHT");
      auto baseRes = underlying.init(allocator, width * height);
      if (baseRes.is_error()) {
        return baseRes;
      }
 
      ensure(underlying.size() == width * height, "BAD UNDERLYING SIZE!");
      this->width  = width;
      this->height = height;
      return success();
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const Slice<const Slice<const char>> binaryStr) {
      ensure(binaryStr.head && binaryStr.len && binaryStr[0].head && binaryStr[0].len, "INVALID BINARY STRING");
      const size_t max_width = binaryStr[0].len;
      for (size_t i = 1; i < binaryStr.len; ++i) {
        ensure(binaryStr[i].head && binaryStr[i].len, "INVALID BINARY STRING ROW");
      }
      return init(allocator, binaryStr.len, max_width, binaryStr);
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const Slice<Slice<const char>> binaryStr) {
      return init(allocator, binaryStr.to_const());
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const size_t height, const size_t width,
                                       const Slice<Slice<const char>> binaryStr) {
      return init(allocator, height, width, binaryStr.to_const());
    }

    Result<void, BitStrInitError> init(mtcore::Allocator &allocator, const size_t height, const size_t width,
                                       const Slice<const Slice<const char>> binaryStr) {
      {
        Slice<const char> curRow;
        auto rowIter = binaryStr.iter();
        while (rowIter.next().copy_if_present(curRow)) {
          char curCell  = '\0';
          auto cellIter = curRow.iter();
          while (cellIter.next().copy_if_present(curCell)) {
            if (curCell != '1' && curCell != '0') {
              return error(BitStrInitError::INVALID_BINARY_STRING);
            }
          }
        }
      }
 
      if (const auto baseRes = init(allocator, height, width); baseRes.is_error()) {
        return error(BitStrInitError::ALLOCATION_FAILED);
      }
 
      Slice<const char> curRow;
      auto rowIter = binaryStr.iter();
      size_t row   = 0;
      while (rowIter.next().copy_if_present(curRow)) {
        mtdefer { ++row; };
        char curCell  = '\0';
        auto cellIter = curRow.iter();
        size_t col    = 0;
        while (cellIter.next().copy_if_present(curCell)) {
          mtdefer { ++col; };
          if (curCell == '1') {
            set(row, col, true);
          }
        }
      }
      return success();
    }

    void deinit(mtcore::Allocator &allocator) {
      underlying.deinit(allocator);
      width  = 0;
      height = 0;
    }

    struct BitsetAccess {
      std::tuple<size_t, size_t> pos;
      Bitset2D &bs;
 
      [[nodiscard]] bool val() const { return bs.at(std::get<0>(pos), std::get<1>(pos)); }
      [[nodiscard]] operator bool() const { return val(); }
      BitsetAccess &set(const bool val) {
        bs.set(std::get<0>(pos), std::get<1>(pos), val);
        return *this;
      }
 
      BitsetAccess &operator=(const bool val) { return set(val); }
      BitsetAccess &operator&=(const bool other) { return set(val() & other); }
      BitsetAccess &operator|=(const bool other) { return set(val() | other); }
      BitsetAccess &operator^=(const bool other) { return set(val() ^ other); }
    };

    [[nodiscard]] bool operator[](std::tuple<size_t, size_t> index) const {
      return at(std::get<0>(index), std::get<1>(index));
    }

    [[nodiscard]] BitsetAccess operator[](std::tuple<size_t, size_t> index) {
      ensure(std::get<0>(index) < height, "OUT OF BOUNDS ACCESS, INVALID ROW");
      ensure(std::get<1>(index) < width, "OUT OF BOUNDS ACCESS, INVALID COL");
      return {index, *this};
    }

    [[nodiscard]] std::tuple<size_t, size_t> size() const { return {height, width}; }

    [[nodiscard]] bool at(size_t row, size_t col) const {
      ensure(row < height, "OUT OF BOUNDS ACCESS, INVALID ROW");
      ensure(col < width, "OUT OF BOUNDS ACCESS, INVALID COL");
      const auto pos = row * width + col;
      return underlying.at(pos);
    }

    Result<Bitset2D, AllocationError> clone(mtcore::Allocator &allocator) {
      auto copyRes = underlying.clone(allocator);
      if (copyRes.is_success()) {
        return copyRes.error();
      }
      auto cpy       = *this;
      cpy.underlying = *copyRes;
      return cpy;
    }

    Result<Bitset2D, AllocationError> clone(mtcore::Allocator &allocator, const size_t newHeight,
                                            const size_t newWidth) {
      Bitset2D res;
      auto initRes = res.init(allocator, newHeight, newWidth);
      if (initRes.is_error()) {
        return initRes.error();
      }
      for (size_t row = 0; row < newHeight && row < height; ++row) {
        for (size_t col = 0; col < newWidth && col < width; ++col) {
          res[{row, col}] = at(row, col);
        }
      }
      return res;
    }

    Bitset2D &set(size_t row, size_t col, bool val) {
      ensure(row < height, "OUT OF BOUNDS ACCESS, INVALID ROW");
      ensure(col < width, "OUT OF BOUNDS ACCESS, INVALID COL");
      const auto pos = row * width + col;
      underlying.set(pos, val);
      return *this;
    }

    Bitset2D &toggle(size_t row, size_t col) {
      ensure(row < height, "OUT OF BOUNDS ACCESS, INVALID ROW");
      ensure(col < width, "OUT OF BOUNDS ACCESS, INVALID COL");
      const auto pos = row * width + col;
      underlying.toggle(pos);
      return *this;
    }

    [[nodiscard]] Optional<std::tuple<size_t, size_t>> first_set() const {
      auto index = underlying.first_set();
      if (index.empty()) {
        return nullopt;
      }
      size_t pos = *index;
      size_t row = pos / width;
      size_t col = pos % width;
      return std::tuple{row, col};
    }

    [[nodiscard]] size_t pop_count() const { return underlying.pop_count(); }

    struct SetBitIter {
      const Bitset2D &bs;
      u64 curMask;
      size_t curIndex;

      Optional<std::tuple<size_t, size_t>> next() {
        while (!curMask && ++curIndex < bs.underlying.bits.len) {
          curMask = bs.underlying.bits[curIndex];
        }
        if (curIndex >= bs.underlying.bits.len) {
          return nullopt;
        }
        mtdefer { curMask ^= static_cast<u64>(0x1) << std::countr_zero(curMask); };
        const size_t pos = 64 * curIndex + std::countr_zero(curMask);
        size_t row       = pos / bs.width;
        size_t col       = pos % bs.width;
        return std::tuple{row, col};
      }
    };

    [[nodiscard]] SetBitIter set_bits() const { return SetBitIter{*this, underlying.bits[0], 0}; }
 
    Bitset2D &operator&=(const Bitset2D &other) {
      size_t row = 0;
      for (; row < other.height && row < height; ++row) {
        size_t col = 0;
        for (; col < other.width && col < width; ++col) {
          this->operator[]({row, col}) &= other[{row, col}];
        }
        for (; col < width; ++col) {
          set(row, col, false);
        }
      }
      for (; row < height; ++row) {
        for (size_t col = 0; col < width; ++col) {
          set(row, col, false);
        }
      }
      return *this;
    }
 
    Bitset2D &operator|=(const Bitset2D &other) {
      for (size_t row = 0; row < other.height && row < height; ++row) {
        for (size_t col = 0; col < other.width && col < width; ++col) {
          this->operator[]({row, col}) |= other[{row, col}];
        }
      }
      return *this;
    }
 
    Bitset2D &operator^=(const Bitset2D &other) {
      for (size_t row = 0; row < other.height && row < height; ++row) {
        for (size_t col = 0; col < other.width && col < width; ++col) {
          this->operator[]({row, col}) ^= other[{row, col}];
        }
      }
      return *this;
    }

    void set_all(bool value) { underlying.set_all(value); }
  };

  template<size_t NumBits = 64>
  struct BitsetFixed {
    std::array<u64, (NumBits + 63) / 64> bytes = {0};
    Slice<u64> bits                            = mut_slice_from(bytes);
 
    void init(u64 val) {
      bits[bits.size() - 1] = val;
      if constexpr (NumBits % 64 != 0) {
        *this <<= (NumBits % 64);
      }
    }

    Result<void, BitStrInitError> init(const Slice<const char> binaryStr) {
      {
        char cur  = '\0';
        auto iter = binaryStr.iter();
        while (iter.next().copy_if_present(cur)) {
          if (cur != '1' && cur != '0') {
            return error(BitStrInitError::INVALID_BINARY_STRING);
          }
        }
      }
 
      char cur     = '\0';
      auto iter    = binaryStr.iter();
      size_t index = 0;
      while (iter.next().copy_if_present(cur)) {
        mtdefer { ++index; };
        if (cur == '1') {
          set(index, true);
        }
      }
      return success();
    }

    struct BitsetAccess {
      size_t pos;
      BitsetFixed &bs;
 
      [[nodiscard]] operator bool() const { return bs.at(pos); }
      [[nodiscard]] bool val() const { return bs.at(pos); }
      BitsetAccess &set(const bool newVal) {
        bs.set(pos, newVal);
        return *this;
      }
 
      BitsetAccess &operator=(const bool val) { return set(val); }
      BitsetAccess &operator&=(const bool other) { return set(val() & other); }
      BitsetAccess &operator|=(const bool other) { return set(val() | other); }
      BitsetAccess &operator^=(const bool other) { return set(val() ^ other); }
    };

    [[nodiscard]] BitsetAccess operator[](const size_t index) {
      ensure(index < NumBits, "OUT OF BOUNDS ACCESS");
      return {.pos = index, .bs = *this};
    }

    [[nodiscard]] bool operator[](const size_t index) const { return at(index); }

    [[nodiscard]] constexpr size_t size() const { return NumBits; }

    [[nodiscard]] bool at(const size_t pos) const {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const auto block  = pos / 64;
      const auto bit    = pos % 64;
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      return (bits[block] & bitMask) != 0;
    }

    BitsetFixed &set(const size_t pos, const bool val) {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const u64 block = pos / 64;
      const u64 bit   = pos % 64;
      ensure(bit + block * 64 == pos, 'BAD POSITION DECONSTRUCT');
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      if (val) {
        bits[block] |= bitMask;
      }
      else {
        bits[block] &= ~bitMask;
      }
      return *this;
    }

    Bitset &toggle(const size_t pos) {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const u64 block   = pos / 64;
      const u64 bit     = pos % 64;
      const u64 bitMask = 0x1 << bit;
      bits[block] ^= bitMask;
      return *this;
    }

    [[nodiscard]] Optional<size_t> last_set() const {
      for (size_t i = bits.len; i > 0; --i) {
        auto indx = i - 1;
        if (bits[indx]) {
          return 64 * indx + 63 - std::countl_zero(bits[indx]);
        }
      }
      return nullopt;
    }

    [[nodiscard]] Optional<size_t> first_set() const {
      for (size_t i = 0; i < bits.len; ++i) {
        if (bits[i]) {
          return 64 * i + std::countr_zero(bits[i]);
        }
      }
      return nullopt;
    }

    [[nodiscard]] size_t pop_count() const {
      size_t count = 0;
      for (size_t i = 0; i < bits.len; ++i) {
        count += std::popcount(bits[i]);
      }
      return count;
    }

    struct SetBitIter {
      const BitsetFixed &bs;
      u64 curMask;
      size_t curIndex;

      Optional<size_t> next() {
        while (!curMask && ++curIndex < bs.bits.len) {
          curMask = bs.bits[curIndex];
        }
        if (curIndex >= bs.bits.len) {
          return nullopt;
        }
        mtdefer { curMask ^= static_cast<u64>(0x1) << std::countr_zero(curMask); };
        const size_t res = 64 * curIndex + std::countr_zero(curMask);
        return res;
      }
    };

    [[nodiscard]] SetBitIter set_bits() const { return SetBitIter{*this, bits[0], 0}; }
 
    BitsetFixed &operator&=(const BitsetFixed &other) {
      size_t i = 0;
      for (; i < other.bits.len && i < bits.len; ++i) {
        bits[i] &= other.bits[i];
      }
      for (; i < bits.len; ++i) {
        bits[i] = 0;
      }
      return *this;
    }
 
    BitsetFixed &operator|=(const BitsetFixed &other) {
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] |= other.bits[i];
      }
      return *this;
    }
 
    BitsetFixed &operator^=(const BitsetFixed &other) {
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] ^= other.bits[i];
      }
      return *this;
    }

    void set_all(const bool value) {
      const u64 mask = value ? std::numeric_limits<u64>::max() : 0;
 
      // For the first n 64-bit segments, just set them all
      for (size_t i = 0; i < bits.len - 1; ++i) {
        bits[i] = mask;
      }
 
      // For the last segment, just set what we have allocated
      for (size_t i = (bits.len - 1) * 64; i < size(); ++i) {
        set(i, value);
      }
    }
 
    BitsetFixed &operator<<=(const size_t amount) {
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = bits.len - i - 1;
          const auto sourceIndex = bits.len - i - 1 - blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = 0; i < blockShift; ++i) {
          bits[i] = 0;
        }
 
        constexpr u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask >> bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) >> (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) << bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask >> (NumBits % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }
 
    BitsetFixed &operator>>=(const size_t amount) {
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = i;
          const auto sourceIndex = i + blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = bits.len - blockShift; i < bits.len; ++i) {
          bits[i] = 0;
        }
 
        const u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask << bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) << (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) >> bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask << (NumBits % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }
  };
 
}  // namespace mtcore
#endif  // MTCORE_BITSET_HPP