常见位运算基础
位运算是底层开发和高性能算法中的利器,虽然语法简单,但掌握其精髓能极大优化代码效率。我们先回顾一下几个核心操作符:
- 左移
<<:低位补 0,相当于乘以 2 的幂。 - 右移
>>:高位补符号位(有符号)或 0(无符号),相当于除以 2 的幂。 - 取反
~:按位翻转。 - 按位与
&:有 0 则 0,常用于清零或提取特定位。 - 按位或
|:有 1 则 1,常用于置位。 - 按位异或
^:相同为 0,不同为 1,无进位加法特性。
理解这些规则后,我们来看几个经典场景。
判断与修改二进制位
假设我们要检查整数 n 的二进制表示中第 x 位是 0 还是 1。思路是将该位移到最低位,再与 1 进行按位与操作。注意运算符优先级,建议加上括号:(n >> x) & 1。
若要将第 x 位强制设为 1,可以利用按位或的特性。构造一个掩码,让 1 左移 x 位,然后与原数进行或运算:n |= (1 << x)。其他位因为与 0 或保持不变,只有目标位变为 1。
同理,将第 x 位设为 0,需要构造一个掩码,让目标位为 0,其余位为 1。这可以通过对 1 << x 取反实现:n &= ~(1 << x)。
位运算常用技巧
这里有两个非常实用的位运算技巧,在面试和工程中经常出现。
1. 提取最右侧的 1
对于任意非零整数 n,表达式 n & -n 可以提取出二进制中最右侧的 1。这是因为负数是原码取反加一, -n 会将最右侧 1 及其左侧全部取反,而右侧 0 保持不变。两者按位与时,仅保留最右侧的 1。
2. 消除最右侧的 1
表达式 n & (n - 1) 可以将最右侧的 1 变为 0。n - 1 会翻转最右侧 1 及其右侧的所有位,按位与操作后,最右侧的 1 被清除,其余位不变。这个技巧常用于统计二进制中 1 的个数。
实战案例解析
判断字符是否唯一
题目要求判断字符串中所有字符是否互不相同,且不使用额外数据结构。利用鸽巢原理,如果字符串长度超过 26(小写字母总数),必然存在重复。我们可以用一个整数作为位图来记录字符出现情况。
class Solution {
public:
bool isUnique(string astr) {
if(astr.size() > 26) return false;
int bitMap = 0;
for( ch : astr) {
i = ch - ;
(((bitMap >> i) & ) == ) ;
bitMap |= ( << i);
}
;
}
};


