0Pricing
Coding Interview Prep · 课时

位运算符：AND、OR、XOR、NOT 与移位

通过真值表和 Python 示例复习六种位运算符，并理解左移和右移与乘以二、除以二之间的关系。

位运算符：AND、OR、XOR、NOT 与移位 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

位运算为何重要

位运算让您可以直接操作整数的二进制表示。许多看似复杂的问题，只要使用正确的位运算技巧就会变得非常简单：例如在 O(n) 时间和 O(1) 空间内寻找缺失的数字、不使用临时变量交换变量，或紧凑地编码子集。面试官使用这些问题来测试您对底层原理的理解和创造性思维。

Python 整数支持任意精度——只要内存允许，它们就可以很大——但位运算在硬件层面始终遵循标准的补码语义。六种运算符都会逐位作用于整数的二进制表示。

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

AND 运算符：位掩码

AND 运算符 (&)仅在两个输入位都为 1 时输出 1。它的主要用途是掩码操作：选出数字中的特定位，同时将其他所有位清零。要检查数字 n 的第 k 位是否为 1，请计算 n & (1 << k)；如果结果非零，则第 k 位为 1。

AND 还可用于清除最低位的 1：n & (n - 1) 会移除最右侧的 1 位。这可用于高效统计置 1 位的数量，以及检查一个数字是否为 2 的幂（2 的幂恰好只有一个置 1 位，因此 n & (n-1) == 0）。

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

OR 运算符：设置位

OR 运算符 (|)只要至少一个输入位为 1，就会输出 1。它的主要用途是将特定位设置为 1，同时不影响其他位。要将数字 n 的第 k 位设置为 1，请使用 n | (1 << k)。移到第 k 位的 1 会打开该位；由于任何数与 0 进行 OR 运算后仍保持不变，其他所有位都会保持不变。

OR 还可用于组合标志：如果您将功能标志表示为独立的位，就可以使用 OR 启用多个标志。例如，READ | WRITE | EXECUTE 会将三个权限位组合成一个整数。

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

XOR 运算符：翻转与差异

XOR 运算符 (^)会在输入位不同时输出 1。XOR 具有三个强大的代数性质：a ^ a = 0（相同输入会相互抵消）、a ^ 0 = a（0 是单位元），并且 XOR 同时满足交换律和结合律。这些性质使 XOR 成为寻找唯一元素的首选工具。

XOR 还可用于翻转特定位：n ^ (1 << k) 会翻转第 k 位，同时保持其他位不变。如果第 k 位原来是 0，它会变为 1；如果原来是 1，它会变为 0。

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

NOT 运算符与补码

NOT 运算符 (~)会翻转所有位。在 Python 中，由于采用补码表示法，~n 等于 -(n+1)。这会让许多人感到意外：~5 = -6，而不是直觉上可能期待的 0b11111010。Python 整数具有无限精度，因此对正数翻转所有位会在补码表示下得到负数。

在实践中，您很少会在 Python 中单独使用 ~ 进行位运算。相反，您可以将它与 AND 结合使用来清除特定位，或计算 ~n & mask，其中 mask 将位宽限制为指定的位数（例如，对 32 位使用 & 0xFFFFFFFF）。

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

左移：乘以 2 的幂

左移运算符 (<<)会将所有位向左移动 k 个位置，并用 0 填充右侧空出的位。这相当于乘以2^k。左移 1 位会使数值翻倍；左移 k 位会使数值乘以 2^k。

在面试题中，左移最常用于创建位掩码：1 << k 会创建一个只有第 k 位为 1 的数字。这是所有位运算操作的基础——设置、清除、翻转和检查单个位，都是从 1 << k 开始的。

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

右移：除以 2 的幂

右移运算符 (>>)会将所有位向右移动 k 个位置，并丢弃最右侧的 k 位。这相当于整除 2^k。Python 的右移始终是算术右移：最左侧的位会用符号位填充（正数为 0，负数为 1）。

一个常见的面试技巧是：要提取数字 n 的第 k 位，请使用 (n >> k) & 1。这会将第 k 位移到位置 0，并通过掩码去除其他所有位。这是检查任意特定位最简洁的方法，无需计算并比较完整的掩码。

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

实用位运算技巧速查表

下面汇总了您在面试中会遇到的最常见位运算惯用写法。请记住这些模式——它们会在数十道题中反复出现：

  • n & 1 — 检查 n 是否为奇数
  • n & (n-1) — 清除最低位的 1
  • n & -n — 提取最低位的 1
  • n | (1 << k) — 设置第 k 位
  • n & ~(1 << k) — 清除第 k 位
  • n ^ (1 << k) — 翻转第 k 位
  • (n >> k) & 1 — 检查第 k 位
# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

统计置 1 位（位计数）

统计整数中 1 位的数量称为人口计数（popcount）。朴素方法会遍历所有位。Brian Kernighan 技巧更快：反复使用 n &= n - 1 清除最低位的 1，并统计循环次数，直到 n 变为 0。每次循环都会恰好移除一个 1 位，因此循环次数正好等于 1 位的数量。

Python 3.10+ 提供了 int.bit_count()，可以直接返回计数结果。在较早的版本中，Kernighan 技巧是标准的手动实现方法。这项技术还可以解决 LeetCode 上的“汉明重量”问题。

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Python 中的位运算：重要注意事项

与 C/Java 不同，Python 整数可以任意大——不存在 32 位或 64 位溢出。这意味着在解决要求 32 位行为的问题时，您必须手动将结果掩码到固定宽度：使用 & 0xFFFFFFFF 只保留低 32 位。

Python 中的 NOT 运算符 ~n 返回 -(n+1)，而不是您可能根据 C 所期待的按位翻转结果。对于 32 位问题，请使用 ~n & 0xFFFFFFFF，或计算 0xFFFFFFFF ^ n，以得到预期的 32 位补码。许多习惯 C 风格位运算的候选人都会被这些差异绊倒。

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

移位运算符与乘法

左移和右移提供了通过 2 的幂进行乘除的极快方法。在硬件上，位移是单条指令即可完成的操作，而乘法和除法需要多个周期。在 Python 中，整数乘法本身已经很高效，但理解这种关系有助于您更清晰地观察位模式。

一个实用恒等式是：要检查 n 是否为 2^k 的倍数，请使用 (n & (2^k - 1)) == 0。掩码 2^k - 1 的低 k 位全为 1；与它进行 AND 运算会得到除以 2^k 后的余数。这与 n % (2^k) 等价，但在基于 C 的语言中速度更快。

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

快速检查

测试您对本课数据结构与算法——编码面试准备相关概念的理解。

课程回顾

本课中您学到了：AND 对位进行掩码，OR 设置位，XOR 翻转位并检测差异，NOT 进行翻转（在 Python 中得到 -(n+1)），移位则通过 2 的幂进行乘除；n & (n-1) 会清除最低位的 1，是检查 2 的幂和统计位数的基础；以及Python 没有固定位宽溢出，因此 32 位问题需要使用 & 0xFFFFFFFF 进行显式掩码。接下来我们将探索 XOR 的自逆性质，用它解决单个数字问题系列。

常见问题解答

「位运算符：AND、OR、XOR、NOT 与移位」课时是免费的吗？

是的 — 「位运算符：AND、OR、XOR、NOT 与移位」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「位运算符：AND、OR、XOR、NOT 与移位」这节课中我会学到什么？

通过真值表和 Python 示例复习六种位运算符，并理解左移和右移与乘以二、除以二之间的关系。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「位运算符：AND、OR、XOR、NOT 与移位」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 位运算符：AND、OR、XOR、NOT 与移位
  2. Single Number 与 XOR 性质
  3. 位掩码：设置、清除、翻转与检查
  4. 位计数、缺失数字与位反转
← 返回 Coding Interview Prep