enumerate/bits.hpp

• View this file on GitHub
• Last update: 2023-05-04 20:25:23+09:00
• Include: #include "enumerate/bits.hpp"

Required by

• graph/count/count_cycle.hpp
• graph/minimum_hamiltonian_cycle.hpp
• graph/steiner_tree.hpp
• knapsack/subset_sum.hpp
• linalg/hafnian.hpp

Verified with

• test/aoj/DPL_2_A.test.cpp
• test/library_checker/matrix/hafnian_of_matrix.test.cpp
• test/mytest/subset_sum.test.cpp
• test/yukicoder/114.test.cpp
• test/yukicoder/2507.test.cpp
• test/yukicoder/4_2.test.cpp
• test_atcoder/abc180e.test.cpp

Code

template <typename F>
void enumerate_bits_32(u32 s, F f) {
  while (s) {
    int i = __builtin_ctz(s);
    f(i);
    s ^= 1 << i;
  }
}

template <typename F>
void enumerate_bits_64(u64 s, F f) {
  while (s) {
    int i = __builtin_ctzll(s);
    f(i);
    s ^= u64(1) << i;
  }
}

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

#line 1 "enumerate/bits.hpp"
template <typename F>
void enumerate_bits_32(u32 s, F f) {
  while (s) {
    int i = __builtin_ctz(s);
    f(i);
    s ^= 1 << i;
  }
}

template <typename F>
void enumerate_bits_64(u64 s, F f) {
  while (s) {
    int i = __builtin_ctzll(s);
    f(i);
    s ^= u64(1) << i;
  }
}

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

Back to top page