bite

位运算是算法中的一个重要专题，充分利用二进制的性质，通过移位、按位与或等操作进行高效计算。以下是位运算的常见操作、技巧及应用：

---

1. 基本位运算操作

操作表：

操作	符号	含义	示例
按位与	&	两个位都为 1 时，结果为 1	5 & 3 = 1 （0101 & 0011 = 0001）
按位或	`	`	只要有一位为 1，结果为 1
按位异或	^	两个位不同，结果为 1，相同为 0	5 ^ 3 = 6 （0101 ^ 0011 = 0110）
按位取反	~	0 变 1，1 变 0	~5 = -6 （按位取反，取补码）
左移	<<	将二进制左移 n 位，低位补 0	5 << 1 = 10 （0101 → 1010）
右移	>>	将二进制右移 n 位，符号位补位（算术右移）	5 >> 1 = 2 （0101 → 0010）
无符号右移	>>>	将二进制右移 n 位，高位补 0（逻辑右移）	Python 不支持，无符号操作可模拟

---

2. 常见位运算技巧

2.1 判断奇偶

# 通过与操作快速判断：
if x & 1 == 0:
    print("偶数")
else:
    print("奇数")

原理：奇数的二进制最低位为 1，偶数为 0。

---

2.2 交换两个数

a, b = 5, 3
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b)  # 输出：3, 5

原理：利用异或的性质：x ^ x = 0 和 x ^ 0 = x。

---

2.3 清零最低位的 1

x = 14  # 二进制：1110
x = x & (x - 1)  # 清除最低位的 1
print(bin(x))  # 输出：0b110

原理：x & (x - 1) 将最低位的 1 置为 0。

---

2.4 判断是否是 2 的幂

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

原理：2 的幂的二进制只有 1 位为 1，如 2=10，4=100。

---

2.5 获取最低位的 1

x = 10  # 二进制：1010
lowest_bit = x & -x
print(bin(lowest_bit))  # 输出：0b10

原理：x & -x 提取最低位的 1。

---

2.6 统计二进制中 1 的个数（汉明重量）

def hamming_weight(x):
    count = 0
    while x:
        x &= x - 1  # 清零最低位的 1
        count += 1
    return count

---

2.7 翻转二进制

def reverse_bits(x):
    res, power = 0, 31
    while x:
        res += (x & 1) << power  # 提取最低位，移到正确位置
        x >>= 1
        power -= 1
    return res

---

3. 进阶应用

3.1 子集生成

利用整数的二进制表示生成集合的所有子集：

def subsets(nums):
    n = len(nums)
    res = []
    for i in range(1 << n):  # 遍历 0 到 2^n - 1
        subset = []
        for j in range(n):
            if i & (1 << j):  # 检查第 j 位是否为 1
                subset.append(nums[j])
        res.append(subset)
    return res

---

3.2 位掩码动态规划

在状态压缩 DP 中，使用位运算表示状态集合。例如，TSP 问题：

• 使用一个整数的二进制表示访问状态；
• 状态转移通过 & 和 | 操作完成。

---

3.3 找两个数组的交集（位图）

利用位图记录数组元素出现的情况：

def intersection(nums1, nums2):
    bitmap = 0
    for num in nums1:
        bitmap |= 1 << num
    res = []
    for num in nums2:
        if bitmap & (1 << num):
            res.append(num)
            bitmap &= ~(1 << num)  # 避免重复
    return res

---

4. 经典题目

题目 1：只出现一次的数字

数组中其他数字都出现两次，找出只出现一次的数字：

def single_number(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

题目 2：只出现一次的两个数字

数组中其他数字都出现两次，找出只出现一次的两个数字：

def single_number(nums):
    xor = 0
    for num in nums:
        xor ^= num
    diff = xor & -xor  # 找到异或结果中最低位的 1
    res = [0, 0]
    for num in nums:
        if num & diff:
            res[0] ^= num
        else:
            res[1] ^= num
    return res

---

位运算是一种直接对二进制位进行操作的运算方式，效率非常高，常用于高效计算、状态压缩、掩码操作等。以下将系统性讲解位运算的基础、性质、技巧和常见思维模式。

---

1. 基础知识

位运算主要有以下几种基本操作：

1.1 按位与 (&)

• 规则：两个二进制位都为 1，则结果为 1，否则为 0。
• 用途：
  • 判断奇偶性：x & 1 == 0 表示 x 为偶数。
  • 提取特定位：x & mask。
  • 清除某些位：x & ~mask。

1.2 按位或 (|)

• 规则：两个二进制位只要有一个为 1，则结果为 1。
• 用途：
  • 设置某些位：x | mask。
  • 合并多个状态。

1.3 按位异或 (^)

• 规则：两个二进制位相同为 0，不同为 1。
• 性质：
  • 交换律和结合律：a ^ b ^ c = a ^ c ^ b。
  • 任意数与 0 异或不变：a ^ 0 = a。
  • 任意数与自身异或为 0：a ^ a = 0。
  • 用途：
    • 交换两个变量：a = a ^ b; b = a ^ b; a = a ^ b;。
    • 寻找唯一数（见下文）。

1.4 按位取反 (~)

• 规则：将每一位取反，1 变 0，0 变 1。
• 用途：
  • 生成掩码：~0 是全 1。
  • 取负数：~x + 1 等于 -x。

1.5 左移 (<<)

• 规则：将二进制位整体左移若干位，右边补 0。
• 用途：
  • 高效乘以 2 的幂：x << n == x * (2^n)。

1.6 右移 (>>)

• 规则：将二进制位整体右移若干位，左侧根据符号位补 0 或补 1（算术右移）。
• 用途：
  • 高效除以 2 的幂：x >> n == x / (2^n)。

---

2. 位运算的性质

2.1 交换律和结合律

• a | b = b | a，a & b = b & a。
• a ^ (b ^ c) = (a ^ b) ^ c。

2.2 分配律

• a & (b | c) = (a & b) | (a & c)。
• a | (b & c) = (a | b) & (a | c)。

2.3 异或与加法的关系

• 异或相当于无进位加法。

---

3. 拆位操作

拆位是对整数的每个位进行独立处理，常见方法包括：

3.1 遍历所有位

for i := 0; i < 32; i++ {
    bit := (x >> i) & 1 // 提取第 i 位
}

3.2 数字的位数

func countBits(x int) int {
    count := 0
    for x > 0 {
        count++
        x >>= 1
    }
    return count
}

3.3 统计二进制中 1 的个数

• 方法 1：逐位检查。

func hammingWeight(x int) int {
    count := 0
    for x > 0 {
        count += x & 1
        x >>= 1
    }
    return count
}

• 方法 2：快速清除最低位的 1。

func hammingWeight(x int) int {
    count := 0
    for x > 0 {
        x &= (x - 1) // 清除最低位的 1
        count++
    }
    return count
}

---

4. 试填与状态压缩

位运算常用于状态压缩，在解决问题时将一个整数的二进制表示用作状态变量。

4.1 子集枚举

n := 3 // 假设有 3 个元素
for mask := 0; mask < (1 << n); mask++ {
    subset := []int{}
    for i := 0; i < n; i++ {
        if mask&(1<<i) != 0 { // 判断第 i 位是否为 1
            subset = append(subset, i)
        }
    }
    fmt.Println(subset)
}

4.2 状态转移（动态规划）

假设有 n 个任务，每个任务只能被完成一次，用位掩码表示任务状态：

dp := make([]int, 1<<n)
for mask := 0; mask < (1 << n); mask++ {
    for j := 0; j < n; j++ {
        if mask&(1<<j) == 0 { // 任务 j 未完成
            next := mask | (1 << j)
            dp[next] = max(dp[next], dp[mask]+score[j])
        }
    }
}

---

5. 常见恒等式

• x & (x - 1)：清除最低位的 1。
• x & -x：保留最低位的 1。
• x | (1 << i)：将第 i 位设为 1。
• x & ^(1 << i)：将第 i 位清零。
• (x >> i) & 1：提取第 i 位。
• x ^ (1 << i)：翻转第 i 位。

---

6. 位运算思维模式

6.1 数学归纳

通过观察二进制表示的规律，找到问题的解法。

6.2 最低有效位操作

利用 x & -x 和 x & (x - 1) 等技巧快速定位、清除最低位。

6.3 状态压缩

将问题的状态映射为二进制位表示，并利用位运算高效更新状态。

---

7. 经典问题

7.1 判断 2 的幂

func isPowerOfTwo(x int) bool {
    return x > 0 && (x & (x - 1)) == 0
}

7.2 找到数组中唯一出现一次的数

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

7.3 计算范围 [m, n] 的按位与

func rangeBitwiseAnd(m int, n int) int {
    shift := 0
    for m < n {
        m >>= 1
        n >>= 1
        shift++
    }
    return m << shift
}

---

通过掌握基础操作、性质、拆位技巧和恒等式，你可以用位运算高效解决许多复杂问题！如果需要某方面的具体实现或思维引导，可以进一步探讨。