位运算小技巧总结

1. 奇偶性快速判断与反转

// 判断奇偶性
bool is_odd = x & 1;  // 真为奇数，假为偶数

// 0/1交替
n ^= 1;

2. 二进制位操作

// (1) 取第k位（从0开始）
int bit = (n >> k) & 1;

// (2) 设置第k位为1
n |= (1 << k);

// (3) 设置第k位为0
n &= ~(1 << k);

3. 位遍历(判断当前位是 1 还是 0 )

while(num) {           // 当num不为0时循环
    if(num & 1) {      
        // 当前位为1的处理逻辑 
    }
    else{
        // 当前位为0的处理逻辑
    }
    num >>= 1;         // 右移一位（相当于除以2）
}

4. 快速计算二进制1的个数（__builtin_popcount）

int cnt = __builtin_popcount(x); // GCC内置函数
// 等价于：
int cnt = 0;
while(x) {
    x &= x - 1;  // 清除最低位的1
    ++cnt;
}

5. 保留最低位的1（lowbit）

int lowbit = x & -x;  // 树状数组核心操作
// 例如：x=6(110) → 2(10)

6. 判断/寻找0位

int t = 1ll;
for (int i = 0; i <= 63;++i){
    if(!(n&t)){     //核心判断条件
        //n的第i位为0
    }

    t <<= 1;
}

7. 判断是否为2的幂

bool is_power_of_two = (x & (x - 1)) == 0;
// 注意特判x=0时为false

8. 位运算优先级口诀

~ > 算术运算 > << >> > & > ^ > |

注意事项

1. 位运算优先级容易出错，建议多用括号
2. 右移时注意符号位（无符号用>>，有符号用>>>）
3. 大数运算记得加1LL防止溢出