第 35 站 · 设计与位运算

实用位运算与数值边界

位运算小工具与快速幂 O(log n)

打开 500 路题单 · 第 35 站 · 14 题

先学: 原地数组
学完去: 没有后续站依赖它。
面试频次: 2 家公司考过 · 面经出现 2 次JPMorgan Chase 1、Upstart 1

先做这道

LC 136只出现一次的数字简单

卡住再看

利用异或的抵消性质消除成对元素，说明交换律和结合律。

要点

x & (x-1) 去掉最低位的 1，x & -x 取出最低位的 1；异或满足 a ^ a = 0，可以找出只出现一次的数。
快速幂把指数按二进制拆开：每轮把底数平方，指数这一位是 1 就乘进结果，O(log exp)。
不超过 20 个元素的集合可以用一个整数当掩码，for (s = mask; s; s = (s-1) & mask) 枚举它的所有非空子集。

易错点

两个 10^9 量级的数相乘会超出 32 位，取模乘法之前先转成 long / long long。
Java 的 >> 会保留符号位，处理负数用无符号右移 >>>；Python 整数无限长，负数要先 & 0xFFFFFFFF。
C++ 里位运算优先级低于比较：x & 1 == 0 实际是 x & (1 == 0)，一定要加括号（Java 会直接编译报错）。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

位运算 · x & (x − 1) 数 1

44 的二进制里有几个 1？

换个输入

x44

02^7

02^6

12^5

02^4

12^3

12^2

02^1

02^0

x−1

·2^7

·2^6

·2^5

·2^4

·2^3

·2^2

·2^1

·2^0

·2^7

·2^6

·2^5

·2^4

·2^3

·2^2

·2^1

·2^0

当前处理已发现 / 已计算答案

x: 44
数到的 1: 0

x = 44，二进制 101100。三行依次是 x、x − 1 和 x & (x − 1)。每轮 x &= x − 1 清掉最低位的 1，轮数就是 1 的个数。

速度

步骤 1 / 8

始终成立x & (x − 1) 恰好清掉最低位的 1，其余位不变。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 136。

Python

def popcount(x: int) -> int:
    """Set bits in a non-negative x (int.bit_count() in Python 3.10+)."""
    count = 0
    while x:
        x &= x - 1  # clear the lowest set bit
        count += 1
    return count


def pow_mod(base: int, exp: int, mod: int) -> int:
    """base ** exp % mod by repeated squaring (the built-in pow(base, exp, mod) does the same)."""
    result, base = 1 % mod, base % mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

C++

// Set bits in x (__builtin_popcount does the same).
int popcount(unsigned x) {
    int count = 0;
    for (; x; x &= x - 1) count++;  // clear the lowest set bit
    return count;
}

// base^exp % mod by repeated squaring; mod < 2^31 keeps every product in 64 bits.
long long powMod(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    for (base %= mod; exp; exp >>= 1) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
    }
    return result;
}

Java

class Solution {
    // Set bits in x (Integer.bitCount does the same).
    int popcount(int x) {
        int count = 0;
        for (; x != 0; x &= x - 1) count++; // clear the lowest set bit
        return count;
    }

    // base^exp % mod by repeated squaring; mod < 2^31 keeps every product in a long.
    long powMod(long base, long exp, long mod) {
        long result = 1 % mod;
        for (base %= mod; exp > 0; exp >>= 1) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
        }
        return result;
    }
}

// popcount counts the set bits in x (bits.OnesCount does the same).
func popcount(x uint) int {
	count := 0
	for ; x != 0; x &= x - 1 { // clear the lowest set bit
		count++
	}
	return count
}

// powMod returns base^exp % mod by repeated squaring; mod < 2^31 keeps every
// product inside an int64.
func powMod(base, exp, mod int) int {
	result := 1 % mod
	for base %= mod; exp > 0; exp >>= 1 {
		if exp&1 == 1 {
			result = result * base % mod
		}
		base = base * base % mod
	}
	return result
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

埃氏筛：从 i² 开始划掉倍数时间 O(n log log n) · 空间 O(n)

要 1..n 里所有质数（计数、预处理最小质因子、质因数分解很多次）：每找到一个质数 i，就把 i², i² + i, … 都划掉；更小的倍数早被更小的质数划过了，所以从 i² 开始，外层也只到 √n。LC 204 计数质数；把布尔数组换成「最小质因子」数组就能 O(log n) 分解质因数。

Python

def count_primes(n: int) -> int:
    """Number of primes below n (LC 204)."""
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i < n:
        if is_prime[i]:
            for j in range(i * i, n, i):  # smaller multiples are already crossed out
                is_prime[j] = False
        i += 1
    return sum(is_prime)

C++

// Number of primes below n (LC 204).
int countPrimes(int n) {
    if (n < 3) return 0;
    vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    for (long long i = 2; i * i < n; i++)
        if (isPrime[i])
            for (long long j = i * i; j < n; j += i) isPrime[j] = false;  // smaller multiples are already crossed out
    return count(isPrime.begin(), isPrime.end(), true);
}

Java

class Solution {
    // Number of primes below n (LC 204).
    int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] composite = new boolean[n]; // composite[k]: k has a smaller prime factor
        int count = 0;
        for (long i = 2; i < n; i++) {
            if (composite[(int) i]) continue;
            count++;
            for (long j = i * i; j < n; j += i) composite[(int) j] = true; // smaller multiples are already crossed out
        }
        return count;
    }
}

// countPrimes returns the number of primes below n (LC 204).
func countPrimes(n int) int {
	if n < 3 {
		return 0
	}
	composite := make([]bool, n) // composite[k]: k has a smaller prime factor
	count := 0
	for i := 2; i < n; i++ {
		if composite[i] {
			continue
		}
		count++
		for j := i * i; j < n; j += i { // smaller multiples are already crossed out
			composite[j] = true
		}
	}
	return count
}

异或抵消，再按最低不同位分组时间 O(n) · 空间 O(1)

成对出现的数里找出只出现一次的那两个（LC 260）：全部异或，成对的抵消，剩下 a ^ b；它的最低位 1（x & -x）就是 a、b 不同的一位，按这一位把所有数分成两组，各自异或就得到 a 和 b。LC 136 只有一个时直接异或；LC 137 出现三次时按位计数模 3。

Python

def single_numbers(nums: list[int]) -> list[int]:
    """The two values that appear once when every other value appears twice (LC 260), smaller first."""
    xor = 0
    for x in nums:
        xor ^= x  # pairs cancel: xor == a ^ b, nonzero because a != b
    low = xor & -xor  # the lowest bit where a and b differ
    a = b = 0
    for x in nums:
        if x & low:  # that bit splits a and b into different groups; pairs stay together
            a ^= x
        else:
            b ^= x
    return sorted([a, b])

C++

// The two values that appear once when every other value appears twice (LC 260), smaller first.
vector<int> singleNumbers(const vector<int>& nums) {
    unsigned xr = 0;
    for (int x : nums) xr ^= x;  // pairs cancel: xr == a ^ b, nonzero because a != b
    unsigned low = xr & (0u - xr);  // the lowest bit where a and b differ (unsigned: no overflow)
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & low) a ^= x;  // that bit splits a and b into different groups; pairs stay together
        else b ^= x;
    }
    return {min(a, b), max(a, b)};
}

Java

class Solution {
    // The two values that appear once when every other value appears twice (LC 260), smaller first.
    int[] singleNumbers(int[] nums) {
        int xor = 0;
        for (int x : nums) xor ^= x; // pairs cancel: xor == a ^ b, nonzero because a != b
        int low = xor & -xor; // the lowest bit where a and b differ
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x & low) != 0) a ^= x; // that bit splits a and b into different groups; pairs stay together
            else b ^= x;
        }
        return new int[] {Math.min(a, b), Math.max(a, b)};
    }
}

// singleNumbers returns the two values that appear once when every other value appears twice, smaller first.
func singleNumbers(nums []int) []int {
	xor := 0
	for _, x := range nums {
		xor ^= x // pairs cancel: xor == a ^ b, nonzero because a != b
	}
	low := xor & -xor // the lowest bit where a and b differ
	a, b := 0, 0
	for _, x := range nums {
		if x&low != 0 { // that bit splits a and b into different groups; pairs stay together
			a ^= x
		} else {
			b ^= x
		}
	}
	return []int{min(a, b), max(a, b)}
}

为什么对

x & (x − 1) 去掉最低位的 1：x − 1 把最低位的 1 变成 0、它右边的 0 全变成 1，再和 x 相与，这一段全变成 0，更高位不变。
快速幂：把指数写成二进制 e = Σ bᵢ·2ⁱ，则 a^e 等于所有 bᵢ = 1 的 a^(2ⁱ) 之积；每轮把底数平方就得到下一个 a^(2ⁱ)，共 O(log e) 轮。
异或找唯一数：异或满足交换律和结合律，且 a ^ a = 0、a ^ 0 = a，所以成对出现的数全部抵消，剩下的就是只出现一次的那个。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

位运算我常用三个技巧。x & (x − 1) 去掉最低位的 1，可以数 1 的个数或判断 2 的幂；异或满足 a ^ a = 0，成对的数会抵消，用来找只出现一次的数。快速幂把指数拆成二进制，每轮底数平方，遇到 1 的位就乘进结果，O(log n) 次乘法。取模时先转成 64 位再相乘，避免溢出。

English

I lean on three bit tricks. x AND (x − 1) clears the lowest set bit, which counts set bits or tests for a power of two, and XOR cancels pairs because a XOR a is zero, which finds the element that appears once. Fast power splits the exponent into bits, squaring the base each round and multiplying it in when the bit is one, for O(log n) multiplications. Under a modulus I widen to 64 bits before multiplying.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

x & (x − 1) 去掉最低位的 1：x − 1 把最低位的 1 变成 0、它右边的 0 全变成 1，再和 x 相与，这一段全变成 0，更高位不变。
快速幂：把指数写成二进制 e = Σ bᵢ·2ⁱ，则 a^e 等于所有 bᵢ = 1 的 a^(2ⁱ) 之积；每轮把底数平方就得到下一个 a^(2ⁱ)，共 O(log e) 轮。
异或找唯一数：异或满足交换律和结合律，且 a ^ a = 0、a ^ 0 = a，所以成对出现的数全部抵消，剩下的就是只出现一次的那个。

小测

5 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

5 道题

对正整数 x，x & (x - 1) == 0 成立意味着什么？
- x 是奇数
- x 是偶数
- x 是 2 的幂
- x 的二进制里 1 和 0 一样多
[7, 3, 5, 3, 7] 中所有数的按位异或结果是？
- 0
- 3
- 7
- 5
在补码表示下，x & -x 的结果是什么？以 x = 12 为例。
- 4
- 8
- 1
- 12
x 是非负整数。循环执行的次数等于？
```
def ones(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count
```
- 固定 32 次
- x 的二进制位数
- x 本身的大小
- x 中 1 的个数
a、b 是正整数，把一次取模看作 O(1)。时间复杂度是？
```
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```
- O(√a)
- O(min(a, b))
- O(log min(a, b))
- O(a + b)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

def popcount(x: int) -> int:
    """Set bits in a non-negative x (int.bit_count() in Python 3.10+)."""
    count = 0

    return result

分档练习

本站在 500 路里的 14 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 5

#	题目	一句话思路
136	只出现一次的数字	利用异或的抵消性质消除成对元素，说明交换律和结合律。
191	位1的个数	用最低有效位清除法统计置位数，明确无符号固定宽度语义。
338	比特位计数	复用较小整数的位计数状态，比较逐数扫描与线性递推。
231	2 的幂	判断是否仅有一个置位，单独处理零和负数。
9	回文数	只反转一半数字检查回文，处理负数、末尾零和奇数位中点。

核心 7

#	题目	一句话思路
190	颠倒二进制位	固定32位逐位重建结果，不能因数值前导零而提前丢失位宽。
137	只出现一次的数字 II	按位计数取模恢复只出现一次的值，处理负数的补码还原。
260	只出现一次的数字 III	用异或差异中的一个置位分组，证明两组各自只剩一个单独元素。
201	数字范围按位与	将连续区间按位与转换为公共二进制前缀，避免逐个枚举大区间。
69	x 的平方根	用整数边界求向下取整平方根，通过除法比较避免乘法溢出。
172	阶乘后的零	按5的幂累计因子数量，避免计算巨大阶乘及遗漏重复因子。
204	计数质数	用筛法批量排除合数，解释从平方开始标记及严格小于n的边界。

进阶 2

#	题目	一句话思路	难度分
371	两整数之和	区分不进位和与进位，理解Python无限精度下的固定宽度掩码处理。
166	分数到小数	模拟长除法并记录余数首次位置，定位循环节并处理符号与整除。

本站 OA 真题 199

Count Powers of k in ReadingsMeta
Count Colliding Object PairsMeta
Three-Digit Numbers With All Distinct DigitsMeta
Closest Land MarkMeta
Count 3 Sister NumbersMeta
System VulnerabilitiesAmazon
Data Dependence SumAmazon
Outlier ValueAmazon
Pascal Triangle EncryptionAmazon
Find Minimum MaximumAmazon

全部 199 道