位运算技巧

基础操作

int a = 0b1010;  // 10

// 位运算
a & 1;           // 取最低位 → 0
a | (1 << 2);    // 第 2 位置 1 → 1110 (14)
a & ~(1 << 1);   // 第 1 位清 0 → 1000 (8)
a ^ (1 << 3);    // 第 3 位翻转 → 0010 (2)

// 移位
a >> 1;          // 右移 = 除以 2 → 5
a << 1;          // 左移 = 乘以 2 → 20

实用技巧

// 判断奇偶
bool isOdd  = n & 1;        // true = 奇
bool isEven = !(n & 1);

// 乘除 2 的幂（编译器会优化，但显式写更清晰）
int half = n >> 1;          // n / 2
int double= n << 1;         // n * 2

// 交换两数（不用临时变量）
a ^= b; b ^= a; a ^= b;    // a ↔ b

// 取绝对值（不用分支）
int mask = n >> 31;         // 算术右移：负数为 -1，正数为 0
int abs  = (n + mask) ^ mask;

// 判断是否为 2 的幂
bool isPowerOf2 = n > 0 && (n & (n - 1)) == 0;
// 8  = 1000, 7 = 0111, 1000 & 0111 = 0000 ✅
// 10 = 1010, 9 = 1001, 1010 & 1001 = 1000 ❌

Brian Kernighan 算法

// 统计二进制中 1 的个数（每次消掉最低位的 1）
int popcount(int n) {
    int cnt = 0;
    while (n) { n &= n - 1; ++cnt; }
    return cnt;
}
// 时间 O(k)，k 为 1 的个数（比逐位检查 O(32) 快）
// 内建替代：std::popcount(n) (C++20)
//            __builtin_popcount(n) (GCC/Clang)

// 取出最低位的 1
int lowbit = n & -n;  // 12 & -12 = 4 (1100 → 0100)

// 消掉最低位的 1
n &= n - 1;

位掩码枚举

// 枚举所有子集（状态压缩 DP 基础）
int mask = 0b1101;  // 全集
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 遍历 mask 的所有非空子集
    // 1101, 1100, 1001, 1000, 0101, 0100, 0001
}

常见面试题

只出现一次的数字

// 数组中其他元素出现两次，一个出现一次，找它
int singleNumber(const vector<int> &nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;  // x ^ x = 0, x ^ 0 = x
    return ans;
}

丢失的数字

// [0, n] 中缺了一个数
int missingNumber(const vector<int> &nums) {
    int ans = nums.size();
    for (int i = 0; i < nums.size(); ++i)
        ans ^= i ^ nums[i];       // 把索引和值全异或
    return ans;
}

两数之和（不用 + 号）

int add(int a, int b) {
    while (b) {
        int carry = (unsigned)(a & b) << 1;  // 进位
        a ^= b;                               // 无进位和
        b = carry;
    }
    return a;
}

颠倒二进制位

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 16);
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
    return n;
}
// 分治法，O(1) 时间

使用场景

场景	技巧
状态标记	bitset<N> / int mask
去重配对	异或 ^（相同归零）
状态压缩 DP	用 int 的低 N 位表示集合
权限系统	READ=1, WRITE=2, EXEC=4 组合
O(1) 空间	用位替代 bool 数组

复杂度注意

// 位运算都是 O(1)，但左移超过类型宽度是 UB
int x = 1 << 31;   // ✅ 在 32 位 int 中
int y = 1 << 32;   // ❌ UB（int 只有 32 位）
int z = 1LL << 32; // ✅ 用 long long