位运算参考文档
计算机基础学习参考 · 涵盖运算符、技巧、XOR 专题（含 X5A Base64 加密方案）与工程实战场景
# 一、基础：二进制与补码
# 1.1 为什么是二进制
计算机底层只有高/低电平两种状态，对应 1 和 0。所有数据（整数、字符、颜色、指令）最终都是二进制位串。
十进制 72 = 二进制 0100 1000 = 十六进制 0x48 = ASCII 'H'
1
十六进制是二进制的缩写：每 4 个二进制位对应 1 个 hex 字符，工程中看位运算结果常用 hex 表达。
# 1.2 原码、反码、补码（负数怎么表示）
以 8 位为例，-5 的表示：
| 编码 | 规则 | -5 的表示 |
|---|---|---|
| 原码 | 最高位符号位 + 绝对值 | 1000 0101 |
| 反码 | 符号位不变，其余取反 | 1111 1010 |
| 补码 | 反码 + 1 | 1111 1011 |
现代计算机整数统一用补码存储，好处：
0只有唯一表示（原码有 +0/-0 两种）- 加法器可直接做减法：
a - b = a + (b的补码) - 符号位参与运算不需要特殊处理
快速手算负数的补码：取绝对值的二进制 → 按位取反 → +1。
例：-1 在任何位宽下都是全 1（8 位 0xFF，32 位 0xFFFFFFFF）。
# 1.3 为什么要引入补码
一句话：让减法变成加法，CPU 只需要一套加法电路。
# 不用补码会怎样（原码的问题）
问题 1：加法直接出错
用原码算 3 - 2，即 3 + (-2)：
0000 0011 ( +3)
+ 1000 0010 ( -2 原码)
─────────────
1000 0101 = -5 ❌ 错！
1
2
3
4
2
3
4
符号位不参与运算，必须额外设计一套"先判符号、再比大小、再决定加减"的逻辑——减法器和加法器得分开造，电路翻倍。
问题 2：零有两种表示
+0 = 0000 0000
-0 = 1000 0000 ← 多出来的零
1
2
2
判断 x == 0 都要判两次，且 8 位只能表示 255 个数（-127 ~ +127）。
# 补码怎么解决
-2 的补码 = 1111 1110，再算同一个式子：
0000 0011 ( +3)
+ 1111 1110 ( -2 补码)
─────────────
1 0000 0001 ← 溢出的进位直接丢弃
↓
0000 0001 = +1 ✅ 对！
1
2
3
4
5
6
2
3
4
5
6
符号位当普通位参与运算，结果自动正确——减法器彻底不需要了。
# 数学本质：模运算（时钟原理）
补码就是同余。12 点钟往回拨 2 小时 = 往前拨 10 小时：
-2 ≡ 254 (mod 256) # 8 位下，-2 用 254 表示
3 - 2 = 3 + 254 = 257 ≡ 1 (mod 256) # 超过 256 绕回来
1
2
2
丢弃最高位进位 = 自动 mod 2ⁿ，硬件上"丢弃"是免费的，什么都不用做。
# 收益总结
| 收益 | 说明 |
|---|---|
| 一套电路 | 加减乘除（乘=多次加）全靠加法器，CPU 更简单便宜 |
| 零唯一 | 0000 0000 只有一个零，x == 0 判断简单 |
| 多表示一个数 | 8 位范围 -128 ~ +127，比原码多一个 -128 |
| 符号位免维护 | 无需任何特殊判断，运算天然正确 |
这也是为什么 ~x == -x-1、n & -n 取 lowbit 这些技巧成立——它们都建立在补码体系上。
# 二、六大位运算符
# 2.1 总览
| 运算符 | 名称 | 规则 | 示例（8位） |
|---|---|---|---|
& | 按位与 AND | 两位都为 1 才为 1 | 0x5A & 0x0F = 0x0A |
\| | 按位或 OR | 任一位为 1 即为 1 | 0x5A \| 0x0F = 0x5F |
^ | 按位异或 XOR | 相同为 0，不同为 1 | 0x5A ^ 0x0F = 0x55 |
~ | 按位取反 NOT | 0 变 1，1 变 0 | ~0x5A = 0xA5（8位） |
<< | 左移 | 低位补 0，每移一位 ×2 | 1 << 3 = 8 |
>> | 右移（带符号） | 高位补符号位，每移一位 ÷2 | -8 >> 1 = -4 |
>>> | 右移（无符号，Java） | 高位补 0 | -1 >>> 28 = 15 |
# 2.2 真值表
| a | b | a & b | a | b | a ^ b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
记忆口诀：
&：都 1 才 1（交集，"且"）|：有 1 就 1（并集，"或"）^：不同才 1（差异检测，"异或"）
# 2.3 各语言示例
# Python
a, b = 0x5A, 0x0F
print(a & b) # 10 (0x0A)
print(a | b) # 95 (0x5F)
print(a ^ b) # 85 (0x55)
print(~a) # -91（Python 整数无限位宽，~x == -x-1）
print(a << 2) # 360
print(a >> 2) # 22
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
// Java（多一个无符号右移）
int a = 0x5A;
System.out.println(~a); // -91
System.out.println(a >> 1); // 45 带符号右移
System.out.println(-1 >>> 28); // 15 无符号右移，高位补 0
1
2
3
4
5
2
3
4
5
# 三、常用技巧清单
# 3.1 判断与检测
# 1. 判断奇偶：最低位是 1 即奇数
if n & 1: print("奇数")
# 2. 判断 2 的幂：二进制中只有一个 1
def is_pow2(n): return n > 0 and n & (n - 1) == 0
# 8 = 1000
# &7 = 0111
# ----> 0000 ✓
# 3. 判断两数异号（不用比较大小，不溢出）
if (x ^ y) < 0: print("异号")
# 4. 判断第 k 位是否为 1（k 从 0 计）
if n & (1 << k): print("第 k 位是 1")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 3.2 位操作三件套（掩码核心操作）
# 置 1：把第 k 位设为 1
n = n | (1 << k)
# 清 0：把第 k 位设为 0
n = n & ~(1 << k)
# 翻转：把第 k 位取反
n = n ^ (1 << k)
# 提取：取低 8 位
low = n & 0xFF
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 3.3 lowbit：取最低位的 1
# n & -n 取出最低位的 1（树状数组核心）
# n = 12 = 1100
# -n 补码 = 0100（取反+1 后与原数只有最低位1相同）
# n & -n = 0100
def lowbit(n): return n & (-n)
1
2
3
4
5
6
2
3
4
5
6
# 3.4 不用临时变量交换两数
a, b = 10, 99
a ^= b
b ^= a # b = (a^b)^b = a
a ^= b # a = (a^b)^a = b
# 注意：Python 中 a, b = b, a 更好；C 中若 a==b 同地址会清零
1
2
3
4
5
2
3
4
5
# 3.5 乘除与优化
n << 1 # n * 2
n << 3 # n * 8
n >> 2 # n / 4（正数向下取整）
# 注意：现代编译器会自动做这个优化，写 n*2 可读性更好
# 取平均防溢出
mid = (low + high) >> 1 # 二分查找经典写法
1
2
3
4
5
6
7
2
3
4
5
6
7
# 3.6 字符技巧
# 大小写转换：字母第 5 位（0x20）控制大小写
ord('A') ^ 0x20 == ord('a') # 65 ^ 32 = 97
chr(ord('H') ^ 0x20) == 'h'
chr(ord('h') ^ 0x20) == 'H'
# 字母转小写（ASCII）: ch | 0x20
# 字母转大写（ASCII）: ch & ~0x20
1
2
3
4
5
6
7
2
3
4
5
6
7
# 四、XOR 专题
# 4.1 四大性质
| 性质 | 公式 | 用途 |
|---|---|---|
| 自逆 | a ^ a = 0 | 加密解密、找落单数 |
| 恒等 | a ^ 0 = a | 初始化 |
| 交换律 | a ^ b = b ^ a | 顺序无关 |
| 结合律 | (a^b)^c = a^(b^c) | 分组无关 |
核心推论：x ^ k ^ k = x ^ (k^k) = x ^ 0 = x —— 异或两次同一个数互相抵消，这是一切 XOR 加密的数学基础。
# 4.2 经典算法题
LeetCode 136 · 只出现一次的数字：数组中其他数都出现两次，找只出现一次的那个。
def single_number(nums):
result = 0
for n in nums:
result ^= n # 成对出现全部抵消，剩下落单的
return result
# [4,1,2,1,2] → 4^1^2^1^2 = 4^(1^1)^(2^2) = 4
1
2
3
4
5
6
2
3
4
5
6
LeetCode 260 · 只出现一次的两个数字：
def single_numbers(nums):
xor_all = 0
for n in nums: xor_all ^= n
# xor_all = a ^ b（a、b 是两个落单数）
rightmost = xor_all & (-xor_all) # 取最低位 1，a、b 在此位必然不同
a = b = 0
for n in nums:
if n & rightmost: a ^= n
else: b ^= n
return [a, b]
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
LeetCode 137 · 只出现一次的数字 II（其他数出现三次）：逐位统计 1 的个数模 3。
# 4.3 XOR 加密混淆方案（X5A Base64）
# 原理
单字节固定 key 的 XOR + Base64 编码，流程：
加密：明文 → 每字节 XOR 0x5A → Base64 编码 → 密文
解密：密文 → Base64 解码 → 每字节 XOR 0x5A → 明文
1
2
2
为什么再套一层 Base64？XOR 后的字节可能不可打印（含 \x00、\n 等），直接放 URL/JSON 会坏；Base64 把任意字节转成 64 个安全字符。
# 完整实现
import base64
KEY = 0x5A # 任意 0x01~0xFF 均可，0x5A 只是惯例（ASCII 'Z'）
def encrypt(plain: str) -> str:
"""加密：XOR 0x5A → Base64"""
xored = bytes([b ^ KEY for b in plain.encode('utf-8')])
return base64.b64encode(xored).decode()
def decrypt(cipher: str) -> str:
"""解密：Base64 → XOR 0x5A（异或自逆，同一操作）"""
xored = base64.b64decode(cipher)
return bytes([b ^ KEY for b in xored]).decode('utf-8')
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 已验证示例
| 明文 | XOR 0x5A 后（hex） | Base64 密文 | 解密 |
|---|---|---|---|
Hello | 12 3f 36 36 35 | Ej82NjU= | Hello ✅ |
拼多多 | — | vNHmv/7Av/7A | 拼多多 ✅ |
逐位分解 'H' ^ 0x5A：
'H' = 0x48 = 0 1 0 0 1 0 0 0
0x5A = 0 1 0 1 1 0 1 0
───────────────── XOR（相同为0，不同为1）
结果 = 0x12 = 0 0 0 1 0 0 1 0
1
2
3
4
2
3
4
# key 的选择
| key | 效果 |
|---|---|
0x5A | 惯例选择，无特殊性 |
任意 0x01~0xFF | 两次异或同样抵消 |
0xFF | 等价于按位取反 |
0x00 | ⚠️ 恒等，无混淆效果 |
多字节循环（如 "KEY"） | 强度略高，仍是统计可破 |
# 多字节 key 版本
def encrypt_multi(plain: str, key: bytes) -> str:
data = plain.encode('utf-8')
xored = bytes([b ^ key[i % len(key)] for i, b in enumerate(data)])
return base64.b64encode(xored).decode()
1
2
3
4
5
2
3
4
5
# 安全性定位（重要）
- ❌ 不是加密：单字节 key 暴力穷举仅 256 次；已知一段明文即可直接推出 key（
明文 ^ 密文 = key）；多字节循环 key 属于重复密钥 XOR，密文足够长时频率分析可破 - ✅ 适用：防肉眼直读——混淆 URL 参数、缓存 key、埋点字段、防爬虫识别简单特征
- 🔐 需要真机密性：请用 AES 等标准算法（Base64 只做传输编码，XOR 只做轻混淆）
# 4.4 其他 XOR 场景
奇偶校验：一串字节全部 XOR，结果为 1 的个数奇偶性。a ^ b ^ c ^ ... 结果的最低位 = 所有数中 1 的总个数的奇偶性，用于校验传输错误。
RAID 5 / 双盘互备：三块盘 D1 ^ D2 = P（校验盘）。任一块损坏，可用另外两块 XOR 恢复：D1 = P ^ D2。
图形 XOR 绘制：早期光标/选区用 XOR 绘制，同一图形画两次即恢复原背景（自逆性）。
# 五、工程实战场景
# 5.1 位掩码：权限与状态标志
用一个整数的每个 bit 表示一个开关，一次传递、一次存储、一次判断多个状态。
// Android Intent flags —— 实际工程源码
intent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK // 0x10000000
| Intent.FLAG_ACTIVITY_CLEAR_TOP); // 0x04000000
// 判断是否包含某 flag
if ((flags & Intent.FLAG_ACTIVITY_NEW_TASK) != 0) { ... }
// 移除某 flag
flags &= ~Intent.FLAG_ACTIVITY_CLEAR_TOP;
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 自定义权限系统
READ, WRITE, EXECUTE, DELETE = 1, 2, 4, 8 # 0001 0010 0100 1000
user_perm = READ | WRITE # 组合：0011 = 3
print(user_perm & WRITE) # 检查：非 0 即有权限
user_perm &= ~WRITE # 回收权限
user_perm |= EXECUTE # 授予权限
1
2
3
4
5
6
7
2
3
4
5
6
7
优点：省内存（1 个 int 存 32 个开关）、组合/判断都是 O(1) 单指令。 缺点：可读性差，需配合常量/枚举命名。
# 5.2 Linux 文件权限
rwxr-xr-- = 111 101 100 = 0o754 = 754。chmod 的数字本质就是 3 组 3 位掩码：
chmod 754 file # 属主 rwx(7) | 组 r-x(5) | 其他 r--(4)
1
# 5.3 网络协议：IP 与子网掩码
# 判断两 IP 是否同一网段
ip1 = int.from_bytes(bytes([192,168,1,100]), 'big')
ip2 = int.from_bytes(bytes([192,168,1,200]), 'big')
mask = int.from_bytes(bytes([255,255,255,0]), 'big')
same_network = (ip1 & mask) == (ip2 & mask) # True
# 网络地址 = IP & 掩码；广播地址 = 网络地址 | ~掩码（取反部分）
1
2
3
4
5
6
7
2
3
4
5
6
7
# 5.4 颜色处理（RGBA）
# 颜色本质是位拼装：0xAARRGGBB
color = 0xFF3366CC # AA=FF RR=33 GG=66 BB=CC
alpha = (color >> 24) & 0xFF # 提取透明度
red = (color >> 16) & 0xFF
green = (color >> 8) & 0xFF
blue = color & 0xFF
# 重组
color = (alpha << 24) | (red << 16) | (green << 8) | blue
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 5.5 位图（Bitmap）：海量数据存在性判断
# 1 GB 内存判断 10 亿个整数是否存在
# 每个数只占 1 bit：10^9 bit ≈ 119 MB
bitmap = bytearray(10**9 // 8 + 1)
def set_bit(n): bitmap[n >> 3] |= (1 << (n & 7))
def get_bit(n): return bitmap[n >> 3] & (1 << (n & 7))
# Redis 的 SETBIT/GETBIT、布隆过滤器的底层都是这个
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 5.6 嵌入式 / 寄存器操作
// 单片机操作寄存器，位运算是唯一手段
GPIOA->MODER &= ~(3 << 10); // 清空第 10-11 位
GPIOA->MODER |= (1 << 10); // 设置为输出模式
GPIOA->ODR ^= (1 << 5); // 翻转第 5 号引脚电平（LED 闪烁）
1
2
3
4
2
3
4
# 5.7 哈希与散列
# 乘法哈希（Fibonacci hashing）：乘以黄金分割常数取高位
def fib_hash(key, bits):
GOLDEN = 0x9E3779B9 # 2^32 / φ
return (key * GOLDEN >> (32 - bits)) & ((1 << bits) - 1)
# HashMap 求桶下标：hash & (capacity - 1)
# capacity 恒为 2 的幂，等价于 hash % capacity 但快得多
1
2
3
4
5
6
7
2
3
4
5
6
7
# 六、语言差异与常见坑
| 语言 | 差异点 |
|---|---|
| Python | 整数无限位宽；~x == -x-1；负数左移不溢出；没有 >>>（-1 >> 1 永远是 -1） |
| Java | 有 >>> 无符号右移；int 固定 32 位；移位超过 31 自动取模（1 << 32 == 1） |
| JavaScript | 位运算强制转 32 位有符号整数；~x == -x-1 可用于 indexOf 判断（if (~idx) 等价 idx !== -1） |
| C/C++ | 有符号数移位负数是未定义行为；1 << 31 溢出 int 需写 1u << 31 |
常见坑：
# 1. 运算优先级：移位低于加减！
1 << 2 + 3 # = 1 << 5 = 32，不是 (1<<2)+3 = 7
# 永远加括号：(1 << 2) + 3
# 2. & 与 == 的优先级：Python 和 C/Java 相反！
# Python：& 高于 ==，n & 1 == 1 是 (n & 1) == 1，安全 ✓
# C/Java：== 高于 &，n & 1 == 1 是 n & (1 == 1)，是 bug ✗
# 跨语言习惯：一律写 (n & 1) == 1
# 3. 负数右移是向下取整（不是向零）
-7 >> 1 == -4 # 而 -7 // 2 == -4 一致，但 int(-7/2) == -3
# 4. XOR 交换同地址清零（C 语言）
# swap(&a, &a) 会让 a 变成 0，Python/Java 无此问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 七、速查表
n & 1 判断奇偶
n & (n-1) == 0 判断 2 的幂
n & -n 取最低位的 1（lowbit）
n >> k & 1 取第 k 位
n | (1 << k) 第 k 位置 1
n & ~(1 << k) 第 k 位清 0
n ^ (1 << k) 第 k 位翻转
n & ((1<<k)-1) 取低 k 位
n << k / n >> k ×2^k / ÷2^k
(x ^ y) < 0 判断异号
x ^ k ^ k = x XOR 自逆（加密基础）
a ^ b ^ a = b 交换/抵消
~x == -x - 1 取反性质
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 附：本文代码验证环境
- Python 3.9+，示例均实际运行验证
- X5A Base64 加密方案验证结果：
Hello → Ej82NjU=、拼多多 → vNHmv/7Av/7A
上次更新: 2026/09/06, 15:42:32