enumerate/bits.hpp

• View this file on GitHub
• Last update: 2025-12-16 20:51:20+09:00
• Include: #include "enumerate/bits.hpp"

Required by

• enumerate/partition.hpp
• graph/count/count_cycle.hpp
• graph/minimum_hamiltonian_cycle.hpp
• graph/steiner_tree.hpp
• knapsack/subset_sum.hpp
• linalg/hafnian.hpp
• setfunc/online/online_or_convolution.hpp
• setfunc/online/online_subset_mobius.hpp
• setfunc/online/online_subset_zeta.hpp
• setfunc/submask_range_query.hpp

Verified with

• test/1_mytest/enum_partitions.test.cpp
• test/1_mytest/subset_sum.test.cpp
• test/2_library_checker/linear_algebra/hafnian_of_matrix.test.cpp
• test/3_yukicoder/114.test.cpp
• test/3_yukicoder/1263.test.cpp
• test/3_yukicoder/1881.test.cpp
• test/3_yukicoder/2507.test.cpp
• test/3_yukicoder/4_2.test.cpp
• test/4_aoj/DPL_2_A.test.cpp

Code

template <typename BS, typename F>
void enumerate_bits_bitset(BS& b, int L, int R, F&& f) {
  if (L >= len(b)) return;
  int p = (b[L] ? L : b._Find_next(L));
  while (p < R) {
    f(p);
    p = b._Find_next(p);
  }
}

template <typename UINT, typename F>
inline void enumerate_all_bit(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  while (s) {
    f(lowbit(s));
    s &= s - 1;
  }
}

template <typename UINT, bool inc_empty, typename F>
inline void enumerate_all_subset(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  for (UINT t = s; t; t = (t - 1) & s) f(t);
  if constexpr (inc_empty) f(0);
}

#line 1 "enumerate/bits.hpp"
template <typename BS, typename F>
void enumerate_bits_bitset(BS& b, int L, int R, F&& f) {
  if (L >= len(b)) return;
  int p = (b[L] ? L : b._Find_next(L));
  while (p < R) {
    f(p);
    p = b._Find_next(p);
  }
}

template <typename UINT, typename F>
inline void enumerate_all_bit(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  while (s) {
    f(lowbit(s));
    s &= s - 1;
  }
}

template <typename UINT, bool inc_empty, typename F>
inline void enumerate_all_subset(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  for (UINT t = s; t; t = (t - 1) & s) f(t);
  if constexpr (inc_empty) f(0);
}

Back to top page