位运算

// 设 a = 0b1100 (12), b = 0b1010 (10)
a & b;   // 0b1000 = 8   位与：两位都为 1 才为 1  —— 常用于"取出/清除某些位"（掩码）
a | b;   // 0b1110 = 14  位或：任一位为 1 即为 1  —— 常用于"置位/合并状态"
a ^ b;   // 0b0110 = 6   异或：两位不同才为 1     —— 常用于"翻转/找不同/消偶"
~a;      // 补码逐位取反：~12 == -13（32 位下 0xFFFFFFF3）
a << 2;  // 左移：低位补 0，等价乘 2^k（可能溢出）
a >> 1;  // 右移：见下方"逻辑 vs 算术"

unsigned u = 0x80000000u; u >> 1;   // 0x40000000  逻辑：高位补 0
int      s = -8;          s >> 1;   // -4          算术：高位补符号位（≈ -8/2）
int      t = -1;          t >> 1;   // 仍是 -1     全 1 右移补 1 还是全 1

// 1) x & (x - 1)：消掉"最低位的那个 1"
//    x    = 0b10110100
//    x-1  = 0b10110011   （最低位 1 变 0，其右侧全变 1）
//    x&.. = 0b10110000   （最低位 1 被清掉）
//    → 判断 2 的幂：x>0 && (x & (x-1)) == 0（2 的幂只有一个 1）

// 2) x & -x（== x & (~x + 1)）：取出"最低位的 1"所代表的值（lowbit）
//    x    = 0b10110100
//    -x   = 0b01001100   （补码 = 取反 + 1）
//    x&-x = 0b00000100   （只保留最低位的 1）—— 树状数组的核心

// 3) a ^ a == 0，a ^ 0 == a，且异或满足交换律/结合律
//    → 一堆数里除某个数出现奇数次、其余偶数次，全部异或起来即为答案（偶数次自我抵消）

int countOnes(unsigned x) {
    int cnt = 0;
    while (x) { x &= (x - 1); cnt++; }   // 每次消掉一个最低位 1
    return cnt;
}
// 也可直接用 __builtin_popcount(x) / std::popcount(x)（C++20）

// I：其余数都出现两次，唯一数出现一次 —— 全体异或，偶次自消
int singleI(std::vector<int>& a) {
    int r = 0;
    for (int x : a) r ^= x;              // a^a=0，剩下的就是那个单身狗
    return r;
}

// II：其余数都出现三次，唯一数出现一次 —— 按位统计模 3
int singleII(std::vector<int>& a) {
    int r = 0;
    for (int b = 0; b < 32; b++) {       // 逐个二进制位
        int sum = 0;
        for (int x : a) sum += (x >> b) & 1;
        if (sum % 3) r |= (1 << b);      // 该位上 1 的总数不是 3 的倍数 → 属于答案
    }
    return r;
}

// III：恰有两个数各出现一次，其余出现两次 —— 异或得 a^b，再用 lowbit 分组
std::pair<int,int> singleIII(std::vector<int>& a) {
    int axorb = 0;
    for (int x : a) axorb ^= x;          // = a ^ b（两个单身狗的异或）
    int low = axorb & -axorb;            // 取 a、b 不同的某一位
    int p = 0, q = 0;
    for (int x : a) (x & low) ? p ^= x : q ^= x;  // 按该位是否为 1 分成两组，各自异或
    return {p, q};
}

std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<std::vector<int>> res;
    for (int mask = 0; mask < (1 << n); mask++) {   // mask 的第 i 位 = 是否选 nums[i]
        std::vector<int> cur;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) cur.push_back(nums[i]);
        res.push_back(cur);
    }
    return res;
}

// 枚举某个掩码 mask 的所有"子掩码"（状压 DP 常用），复杂度 O(3^n)：
// for (int sub = mask; sub; sub = (sub - 1) & mask) { ... }  // sub 依次遍历 mask 的非空子集

std::vector<int> grayCode(int n) {
    std::vector<int> res;
    for (int i = 0; i < (1 << n); i++)
        res.push_back(i ^ (i >> 1));     // 二进制 → 格雷码：异或自身右移一位
    return res;
}

int hammingDistance(int x, int y) {
    return countOnes(x ^ y);             // 先 ^ 找出不同位，再数 1
}

x & 1;              // 判奇偶（1=奇）
x | (1 << k);       // 把第 k 位置 1
x & ~(1 << k);      // 把第 k 位清 0
x ^ (1 << k);       // 翻转第 k 位
(x >> k) & 1;       // 取第 k 位
x & (x - 1) == 0;   // （x>0 时）判断是否 2 的幂