位运算基础与经典算法题解析

常见位运算

1. 基础位运算

• << 左移操作符
• >> 右移操作符
• ~ 取反
• & 按位与：有 0 就是 0
• | 按位或：有 1 就是 1
• ^ 按位异或：相同为 0，不同则为 1（无进位相加）

示例：

0 1 0
0 1 1
-------
0 1 0 按位与结果
0 1 1 按位或结果
0 0 1 按位异或结果

2. 确定二进制表示中的第 x 位是 0 还是 1

假设下标从 0 开始。若需判断第 x 位，先将数右移 x 位，再与 1 进行按位与操作。

代码：(n >> x) & 1

若结果为 1，则该位为 1；否则为 0。建议运算符优先级处加括号。

3. 将第 x 位修改成 1

利用按位或特性。将 1 左移 x 位后与原数按位或。

代码：n |= (1 << x)

4. 将第 x 位修改成 0

利用按位与特性。将 1 左移 x 位后取反，再与原数按位与。

代码：n &= (~(1 << x))

5. 位图

本质是一个哈希表，用于高效存储布尔状态。

6. 提取最右侧的 1

使用 n & -n。 原理：负数是原数按位取反再加 1。最右侧 1 及其右侧位不变，左侧位取反。两者按位与即可保留最右侧 1。

代码：n & -n

7. 干掉最右侧的 1

将最右侧的 1 变为 0。

代码：n & (n - 1)

8. 异或运算律

• a ^ 0 = a
• a ^ a = 0
• a ^ b ^ c = a ^ (b ^ c)

判断字符是否唯一

题目链接

实现一个算法，确定字符串 s 的所有字符是否全都不同。

限制：

• 0 <= len(s) <= 100
• s[i] 仅包含小写字母
• 不使用额外数据结构会加分。

解法一：Hash 扫描字符串统计出现次数，若大于 1 则返回 false。时间复杂度 O(N)，空间复杂度 O(N)。

解法二：位图 + 鸽巢原理 若字符串长度超过 26，必有重复字符，直接返回 false。 使用整型变量作为位图，遍历字符，检查对应位是否为 1。

class Solution {
public:
    bool  {
        (astr.() > )  ;
         bitMap = ;
        ( ch : astr) {
             i = ch - ;
            (((bitMap >> i) & ) == )  ;
            bitMap |= ( << i);
        }
         ;
    }
};