bitset::find_prev
(misc/bitset-find-prev.hpp)

• View this file on GitHub
• Last update: 2021-04-19 21:35:56+09:00
• Include: #include "misc/bitset-find-prev.hpp"
• Link: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/bitset

Verified with

• verify/verify-unit-test/bitset-find-prev.test.cpp

Code

#pragma once

// 参考：https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/bitset
template <size_t Nb>
struct Bitset : bitset<Nb> {
  template <typename... Args>
  Bitset(Args... args) : bitset<Nb>(args...) {}

  static constexpr int N = Nb;
  static constexpr int array_size = (Nb + 63) / 64;

  union raw_cast {
    array<uint64_t, array_size> a;
    Bitset b;
  };

  int _Find_prev(size_t i) const {
    if (i == 0) return -1;
    if ((*this)[--i] == true) return i;
    size_t M = i / 64;
    const auto& a = ((raw_cast*)(this))->a;
    uint64_t buf = a[M] & ((1ull << (i & 63)) - 1);
    if (buf != 0) return M * 64 + 63 - __builtin_clzll(buf);
    while (M--) {
      if (a[M] != 0) return M * 64 + 63 - __builtin_clzll(a[M]);
    }
    return -1;
  }

  inline int _Find_last() const { return _Find_prev(N); }
};

/**
 * @brief bitset::find_prev
 */

#line 2 "misc/bitset-find-prev.hpp"

// 参考：https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/bitset
template <size_t Nb>
struct Bitset : bitset<Nb> {
  template <typename... Args>
  Bitset(Args... args) : bitset<Nb>(args...) {}

  static constexpr int N = Nb;
  static constexpr int array_size = (Nb + 63) / 64;

  union raw_cast {
    array<uint64_t, array_size> a;
    Bitset b;
  };

  int _Find_prev(size_t i) const {
    if (i == 0) return -1;
    if ((*this)[--i] == true) return i;
    size_t M = i / 64;
    const auto& a = ((raw_cast*)(this))->a;
    uint64_t buf = a[M] & ((1ull << (i & 63)) - 1);
    if (buf != 0) return M * 64 + 63 - __builtin_clzll(buf);
    while (M--) {
      if (a[M] != 0) return M * 64 + 63 - __builtin_clzll(a[M]);
    }
    return -1;
  }

  inline int _Find_last() const { return _Find_prev(N); }
};

/**
 * @brief bitset::find_prev
 */

Back to top page