数学重学 - 08 进制与位运算

这是 数学重学路线图 阶段二的子页面

📌 已有相关笔记：进制与编码、运算符，本页从数学角度重新梳理并补充 Python 实战

为什么要学进制与位运算

计算机的一切数据，归根结底都是 0 和 1

理解进制 → 才能看懂内存地址、颜色值、文件头、网络协议

理解位运算 → 才能看懂子网掩码、权限标记、布隆过滤器、XOR 加密

安全方向：IP/子网计算、shellcode 分析、XOR 编码绕过

大数据方向：bitmap 去重、布隆过滤器、压缩编码

后端方向：权限位、feature flag、高性能计算

核心概念：进制的本质

逢 N 进一

十进制是因为人有 10 根手指，所以逢十进一

二进制是因为电路只有 开/关 两种状态，所以逢二进一

十六进制是程序员的 速记法，把 4 位二进制缩成 1 位

本质上，任何正整数 N ≥ 2 都可以做进制的基数

二进制（Binary, base-2）

只有 0 和 1 两个数字

每一位代表 2 的某次幂

例：1011₂ 怎么算？

1×2³ + 0×2² + 1×2¹ + 1×2⁰

= 8 + 0 + 2 + 1

= 11（十进制）

前缀表示：Python 中用 0b 前缀，如 0b1011

十六进制（Hexadecimal, base-16）

数字：0-9, A-F（A=10, B=11, …, F=15）

每 1 位十六进制 = 4 位二进制，这就是为什么程序员爱用它——简短！

例：0xFF = 1111 1111₂ = 255

例：颜色 #FF5733 = R=255, G=87, B=51

前缀表示：Python 中用 0x 前缀

八进制（Octal, base-8）

数字：0-7

最常见场景：Linux 文件权限

r(读)=4, w(写)=2, x(执行)=1

chmod 755 = 所有者 rwx(7) + 组 r-x(5) + 其他 r-x(5)

7 = 4+2+1 = 111₂ → 读+写+执行

5 = 4+0+1 = 101₂ → 读+执行

前缀表示：Python 中用 0o 前缀，如 0o755

进制转换方法

十进制 → 二进制：除 2 取余法

把十进制数不断除以 2，记录余数，最后把余数 倒序排列

例：13 → 二进制

13 ÷ 2 = 6 余 1

6 ÷ 2 = 3 余 0

3 ÷ 2 = 1 余 1

1 ÷ 2 = 0 余 1

倒序：1101₂

二进制 → 十进制：按权展开

每一位 × 对应的 2 的幂次，然后求和

1101₂ = 1×8 + 1×4 + 0×2 + 1×1 = 13

二进制 ↔ 十六进制：四位一组

二→十六：从右往左每 4 位分一组，不足补 0

例：1010 1111₂ → A F → 0xAF

十六→二：每 1 位展开成 4 位二进制

例：0x3C → 0011 1100₂

人话总结

十进制是给人看的

二进制是给机器看的

十六进制是给程序员看的（二进制的缩写版）

八进制主要活在 Linux 权限里

位运算详解

AND（与）&

规则：两个都是 1 才是 1

真值表：

0 & 0 = 0

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

直觉：像筛子，只留下两者共同为 1 的位

核心应用：掩码提取

IP 地址与子网掩码做 AND → 得到网络地址

192.168.1.100 & 255.255.255.0 = 192.168.1.0

OR（或）|

规则：只要有一个 1 就是 1

直觉：合并，把两者的 1 都保留

核心应用：标志位设置

权限合并：READ | WRITE = READ_WRITE

XOR（异或）^

规则：相同为 0，不同为 1

直觉：找不同

重要性质：

a ^ a = 0（自己和自己异或为 0）

a ^ 0 = a（和 0 异或不变）

满足交换律和结合律

核心应用：

加密基础：明文 ^ 密钥 = 密文，密文 ^ 密钥 = 明文

不用临时变量交换两个数

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

NOT（取反）~

规则：0 变 1，1 变 0

Python 中 ~n = -(n+1)，因为用补码表示

左移 << 和右移 >>

左移 k 位 = ×2^k

右移 k 位 = ÷2^k（向下取整）

例：5 << 2 = 20（5 × 4）

例：20 >> 2 = 5（20 ÷ 4）

比乘除法快，编译器经常做这个优化

位运算经典技巧

判断奇偶

n & 1：结果为 1 则奇数，为 0 则偶数

原理：二进制最后一位是 1 就是奇数

判断是否 2 的幂

n & (n - 1) == 0（且 n > 0）

原理：2 的幂的二进制只有 1 个 1，减 1 后全变成 1，AND 后为 0

例：8 = 1000₂，7 = 0111₂，1000 & 0111 = 0000 ✓

取最低位的 1

n & (-n)

原理：-n 是 n 的补码（取反加一），只有最低位的 1 会保留

例：12 = 1100₂，-12 的补码 = 0100₂，1100 & 0100 = 0100 = 4

清除最低位的 1

n & (n - 1)

可以用来数二进制中有多少个 1（不断清除直到变 0）

Python 代码实战

进制转换

# 十进制 → 各种进制
n = 255
print(f"十进制: {n}")
print(f"二进制: {bin(n)}")        # 0b11111111
print(f"八进制: {oct(n)}")        # 0o377
print(f"十六进制: {hex(n)}")      # 0xff

# 去掉前缀的写法
print(f"二进制: {n:b}")           # 11111111
print(f"八进制: {n:o}")           # 377
print(f"十六进制: {n:x}")         # ff
print(f"十六进制(大写): {n:X}")   # FF

# 各种进制 → 十进制
print(int('11111111', 2))         # 255
print(int('377', 8))              # 255
print(int('ff', 16))              # 255

# 手动实现除2取余法
def to_binary(n):
if n == 0:
    return '0'
bits = []
while n > 0:
    bits.append(str(n % 2))
    n //= 2
return ''.join(reversed(bits))

print(to_binary(13))              # 1101

IP 地址与子网掩码计算

import ipaddress

def ip_subnet_calc(ip_str, mask_str):
"""用位运算手动计算网络地址和广播地址"""
# 把 IP 和掩码转成 32 位整数
ip_parts = [int(x) for x in ip_str.split('.')]
mask_parts = [int(x) for x in mask_str.split('.')]

ip_int = (ip_parts[0] << 24) | (ip_parts[1] << 16) | \
         (ip_parts[2] << 8) | ip_parts[3]
mask_int = (mask_parts[0] << 24) | (mask_parts[1] << 16) | \
           (mask_parts[2] << 8) | mask_parts[3]

# 网络地址 = IP & 掩码
network_int = ip_int & mask_int
# 广播地址 = 网络地址 | ~掩码
broadcast_int = network_int | (~mask_int & 0xFFFFFFFF)
# 主机数 = 广播地址 - 网络地址 - 1
host_count = broadcast_int - network_int - 1

def int_to_ip(n):
    return f"{(n>>24)&0xFF}.{(n>>16)&0xFF}.{(n>>8)&0xFF}.{n&0xFF}"

print(f"IP 地址:    {ip_str}")
print(f"子网掩码:  {mask_str}")
print(f"网络地址:  {int_to_ip(network_int)}")
print(f"广播地址:  {int_to_ip(broadcast_int)}")
print(f"可用主机数: {host_count}")
print(f"IP 二进制:  {ip_int:032b}")
print(f"掩码二进制: {mask_int:032b}")

ip_subnet_calc("192.168.1.100", "255.255.255.0")

# 用标准库验证
net = ipaddress.IPv4Network("192.168.1.0/24")
print(f"\n标准库验证:")
print(f"网络地址: {net.network_address}")
print(f"广播地址: {net.broadcast_address}")
print(f"主机数: {net.num_addresses - 2}")

XOR 加密 / 解密

def xor_encrypt(plaintext: str, key: str) -> bytes:
"""XOR 加密：简单但能说明原理"""
key_bytes = key.encode()
plain_bytes = plaintext.encode()
encrypted = bytes([
    p ^ key_bytes[i % len(key_bytes)]
    for i, p in enumerate(plain_bytes)
])
return encrypted

def xor_decrypt(cipher: bytes, key: str) -> str:
"""XOR 解密：再 XOR 一次密钥就还原了"""
key_bytes = key.encode()
decrypted = bytes([
    c ^ key_bytes[i % len(key_bytes)]
    for i, c in enumerate(cipher)
])
return decrypted.decode()

message = "Hello, Security!"
key = "mykey"
encrypted = xor_encrypt(message, key)
print(f"密文(hex): {encrypted.hex()}")
decrypted = xor_decrypt(encrypted, key)
print(f"解密: {decrypted}")  # Hello, Security!

位图(Bitmap)去重

class Bitmap:
"""用位图实现大规模整数去重，极省内存"""
def __init__(self, max_val):
    # 每个 int 存 64 位（Python int 无限大，但我们手动管理）
    self.size = max_val
    # 用 bytearray，每个字节 8 位
    self.bits = bytearray((max_val >> 3) + 1)

def add(self, num):
    byte_idx = num >> 3       # num // 8
    bit_idx = num & 7         # num % 8
    self.bits[byte_idx] |= (1 << bit_idx)

def contains(self, num):
    byte_idx = num >> 3
    bit_idx = num & 7
    return bool(self.bits[byte_idx] & (1 << bit_idx))

def memory_usage_mb(self):
    return len(self.bits) / (1024 * 1024)

# 测试：对 1000 万个 ID 去重
import random
bm = Bitmap(10_000_000)
ids = [random.randint(0, 9_999_999) for _ in range(5_000_000)]

for id_ in ids:
bm.add(id_)

unique_count = sum(1 for i in range(10_000_000) if bm.contains(i))
print(f"唯一 ID 数: {unique_count}")
print(f"内存占用: {bm.memory_usage_mb():.2f} MB")
# 1000 万个 ID 只需要约 1.2 MB！

权限位标记（后端常用）

# 用一个整数表示多个权限——后端 feature flag 的基础
READ    = 1 << 0  # 0001 = 1
WRITE   = 1 << 1  # 0010 = 2
DELETE  = 1 << 2  # 0100 = 4
ADMIN   = 1 << 3  # 1000 = 8

def grant(perms, flag):
"""授予权限：用 OR"""
return perms | flag

def revoke(perms, flag):
"""撤销权限：用 AND NOT"""
return perms & ~flag

def has_perm(perms, flag):
"""检查权限：用 AND"""
return bool(perms & flag)

# 模拟
user_perms = 0
user_perms = grant(user_perms, READ)
user_perms = grant(user_perms, WRITE)
print(f"权限值: {user_perms} = {user_perms:04b}")  # 0011 = 3
print(f"有读权限? {has_perm(user_perms, READ)}")    # True
print(f"有删权限? {has_perm(user_perms, DELETE)}")   # False

user_perms = revoke(user_perms, WRITE)
print(f"撤销写后: {user_perms} = {user_perms:04b}") # 0001 = 1

实际应用场景

安全方向

IP 地址与子网掩码计算（网络安全基础中的基础）

XOR 加密 / 编码绕过（恶意软件常用 XOR 混淆 payload）→ 详见 密码学数学

shellcode 分析需要看懂十六进制

二进制文件头识别（magic bytes：PDF = %PDF = 25 50 44 46）

大数据方向

布隆过滤器：用多个哈希函数对应位图中的位，判断元素是否”可能存在”

位图去重：10 亿个用户 ID 只需 ~125 MB 内存

压缩编码：Huffman 编码、变长编码都是位级操作

后端方向

权限位标记：一个 int 存 32 个布尔开关，比 32 个字段高效得多

feature flag：用位运算控制功能开关

哈希函数内部：大量使用位移和异或

生活类比

进制就像重量单位：1斤=10两（十进制）、1字节=8位（八进制/二进制）

位运算就像开关面板：AND=两个开关都开灯才亮，OR=任一开关开灯就亮

常见误区

❌ 误区1：二进制只在底层有用，高级语言不需要

✅ 网络编程、加密、权限设计到处都是，不理解位运算会踩坑

❌ 误区2：左移就是乘 2，任何情况都对

✅ 溢出时不对。Python 整数无限大所以没这个问题，但 C/Java 有

❌ 误区3：XOR 加密很安全

✅ 单次 XOR 非常弱（频率分析可破），只是加密的基础组件

❌ 误区4：~n 就是把所有位取反变成正数

✅ 在补码系统中 ~n = -(n+1)，比如 ~5 = -6

练习题

题1：进制转换

把十进制 200 转成二进制、八进制、十六进制

把二进制 10110011 转成十进制和十六进制

答案：

200 = 0b11001000 = 0o310 = 0xC8

10110011₂ = 179 = 0xB3

题2：位运算基础

计算：0b1010 & 0b1100 = ?

计算：0b1010 | 0b1100 = ?

计算：0b1010 ^ 0b1100 = ?

答案：

0b1000 = 8

0b1110 = 14

0b0110 = 6

题3：子网计算

IP 10.0.5.200，子网掩码 255.255.254.0（/23）

求网络地址、广播地址、可用主机数

答案：

网络地址：10.0.4.0

广播地址：10.0.5.255

可用主机数：510

题4：找唯一数

数组 [2, 3, 5, 3, 2] 中只有一个数出现了一次，用 XOR 找出来

用 Python 一行代码实现

答案：

全部 XOR：2^3^5^3^2 = (2^2)^(3^3)^5 = 0^0^5 = 5

from functools import reduce; reduce(lambda a,b: a^b, [2,3,5,3,2])

题5：权限设计

设计一个权限系统，用位运算实现：查看(1)、编辑(2)、删除(4)、管理(8)

一个用户有”查看+编辑”权限，如何用一个数字表示？

如何判断该用户是否有删除权限？

答案：

查看+编辑 = 1 | 2 = 3

判断删除权限：3 & 4 == 0 → 没有删除权限

---

上一章	目录	下一章
07-数据素养	数学重学路线图	09-模运算与整除