setfunc/xor_submask_lower_bound.hpp

• View this file on GitHub
• Last update: 2026-08-19 06:34:57+09:00
• Include: #include "setfunc/xor_submask_lower_bound.hpp"

Depends on

• other/bit.hpp

Code

#include "other/bit.hpp"

// a <= b xor (submask S) となる中で右辺の最小
// なければ UINT(-1)
template <typename UINT>
UINT xor_submask_lower_bound(UINT a, UINT b, UINT S) {
  // a <= (b ^ submask(S)), minimize rhs
  b &= ~S;
  if (a <= b) return b;
  u32 c = b | S;
  if (a > c) return -1;
  u32 D = (a ^ b) & ~S;
  if (D == 0) return a;
  int k = topbit(D);
  if ((b >> k) & 1) {
    b |= (a & S) & ~full_mask(k + 1);
    return b;
  }
  u32 X = S & ~a;
  X &= ~full_mask(k + 1);
  k = lowbit(X);
  b |= (a & S) & ~full_mask(k + 1);
  b |= u32(1) << k;
  assert(a <= b);
  return b;
};

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) { return n == 64 ? -1ULL : (1ULL << n) - 1; }

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "setfunc/xor_submask_lower_bound.hpp"

// a <= b xor (submask S) となる中で右辺の最小
// なければ UINT(-1)
template <typename UINT>
UINT xor_submask_lower_bound(UINT a, UINT b, UINT S) {
  // a <= (b ^ submask(S)), minimize rhs
  b &= ~S;
  if (a <= b) return b;
  u32 c = b | S;
  if (a > c) return -1;
  u32 D = (a ^ b) & ~S;
  if (D == 0) return a;
  int k = topbit(D);
  if ((b >> k) & 1) {
    b |= (a & S) & ~full_mask(k + 1);
    return b;
  }
  u32 X = S & ~a;
  X &= ~full_mask(k + 1);
  k = lowbit(X);
  b |= (a & S) & ~full_mask(k + 1);
  b |= u32(1) << k;
  assert(a <= b);
  return b;
};

Back to top page