前言

位运算在业务代码中已经很少用了，但面试刷题经常会用到，这里复习下

一、基础位运算操作

1. 按位与 (&)

规则：两位都是1，结果才是1，否则为0
---
  0 & 0 = 0
  0 & 1 = 0
  1 & 0 = 0
  1 & 1 = 1

示例：

  1010 (10)
& 1100 (12)
------
  1000 (8)

2. 按位或 (|)

规则：两位有一个是1，结果就是1
---
  0 | 0 = 0
  0 | 1 = 1
  1 | 0 = 1
  1 | 1 = 1

示例：

  1010 (10)
| 1100 (12)
------
  1110 (14)

3. 按位异或 (^)

规则：两位不同为1，相同为0
---
  0 ^ 0 = 0
  0 ^ 1 = 1
  1 ^ 0 = 1
  1 ^ 1 = 0

示例：

  1010 (10)
^ 1100 (12)
------
  0110 (6)

特性：

a ^ a = 0
a ^ 0 = a
a ^ b ^ b = a  (异或两次等于本身)
满足交换律和结合律

4. 按位取反 (~)

规则：0变1，1变0
---
~ 1010 = 0101

注意：Go中的取反

~1 => ^1  // Go中没有使用~符，其等价于 ^(-1)

5. 左移 (<<)

规则：左边补0，相当于 ×2^n
---
1010 << 1 = 10100  (10 << 1 = 20 = 10 × 2^1)
1010 << 2 = 101000 (10 << 2 = 40 = 10 × 2^2)

常见要点

6. 右移 (>>)

规则：右边移出，左边补符号位，相当于 ÷2^n
---
1010 >> 1 = 0101  (10 >> 1 = 5 = 10 ÷ 2^1)
1010 >> 2 = 0010  (10 >> 2 = 2 = 10 ÷ 2^2)

二、常用位运算技巧

1. 判断奇偶

// 判断 n 是否为偶数
if n & 1 == 0 {
    // 偶数
}

// 判断 n 是否为奇数
if n & 1 == 1 {
    // 奇数
}

原理： 二进制最后一位是1表示奇数，0表示偶数

2. 取最低位的1

// 获取 n 最低位的1
lowbit := n & (-n)

// 移除 n 最低位的1
n = n & (n - 1)

示例：

n = 12 = 1100
-n = -12 = (补码表示)
n & (-n) = 100 = 4  // 最低位的1

n = 14 = 1110
n & (n-1) = 14 & 13 = 1110 & 1101 = 1100  // 移除最低位1

3. 判断2的幂

// 判断 n 是否是2的幂
if n > 0 && (n & (n-1)) == 0 {
    // 是2的幂 (1, 2, 4, 8, 16, ...)
}

原理： 2的幂二进制只有1个1

4. 获取第i位

// 获取第i位（最低位为第0位）
bit := (n >> i) & 1

// 设置第i位为1
n = n | (1 << i)

// 设置第i位为0
n = n & (^(1 << i))

5. 交换两数

// 不使用临时变量交换
a = a ^ b
b = a ^ b  // b = (a^b)^b = a
a = a ^ b  // a = (a^b)^a = b

前言

一、基础位运算操作