位运算

(1) 判断奇偶

if(x&1) cout<<"odd"; // 奇数
else cout<<"even";   // 偶数

(2) 取二进制某一位

(x>>k)&1  // 取第 k 位 (0-based)

(3) 设置某一位为 1

x |= (1<<k);

(4) 清零某一位

x &= ~(1<<k);

(5) 翻转某一位

x ^= (1<<k);

3. 与低位相关的技巧

(1) 取最低位的 1

x & -x

例：12 (1100) → 4 (0100)

(2) 去掉最低位的 1

x &= (x-1);

例：12 (1100) → 8 (1000)

(3) 判断是否是 2 的幂

(x>0 && (x&(x-1))==0)

4. 子集枚举

(1) 枚举 n 位二进制的所有子集

for(int s=0;s<(1<<n);s++){...}

(2) 枚举某集合 S 的所有子集

for(int sub=S;sub;sub=(sub-1)&S){...}

最后还需要单独考虑空集。

5. 位运算加速

• 快速乘除以 2：
  x<<1 = x*2
x>>1 = x/2

• 交换两个数（不使用临时变量）：

a^=b; b^=a; a^=b;

• 取绝对值（int）：

(x^(x>>31))-(x>>31)