位运算与数学

位运算是很多候选人突然沉默的地方。运算符本身简单到不能再简单,但 two's complement、符号扩展、悄无声息的 32 位溢出,能把「送分题」变成能编译、能运行、却答错的题。这一课从最底层的机器表示讲起——一个 int 到底怎么存、每个运算符到底在干什么——然后把这套词汇花在面试常客上:数 1 的个数、XOR 找单身数、2 的幂、翻转比特、进制转换,以及那些穿着算术外衣、骨子里都是溢出题的「数学题」(LC 7 / 29 / 69 / 166 / 172)。

一个整数在内存里到底怎么存

Java 的 int 是 32 位——4 个字节——而且默认有符号。最高位是符号位(most significant bit),最低位是 least significant bit。就是这一个符号位,让取值范围不对称:-2^31 到 2^31 - 1。转换很机械:二进制 → 十进制是 2 的幂加权求和(每一位乘 2^i),十进制 → 二进制是不断 /2 取余、把余数倒着读。

解锁负数的关键是 two's complement(补码):取负 = 每一位取反,再加 1。同一个配方双向都成立——把 2 变成 -2,也把 -2 变回 2。Integer.MIN_VALUE 是孤零零一个符号位 1000…0,它没有对应的正数——这正是 Math.abs(Integer.MIN_VALUE) 溢出、返回值仍是负数的原因。把这颗地雷记牢;下面一半的「数学题」都是在绕开它走路。

符号位                                       最低位
   |                                          |
   v                                          v
   1 0 0 0 0 0 0 0 . . . 0 0 0 0 0 0 0  =  Integer.MIN_VALUE = -2^31
   0 1 1 1 1 1 1 1 . . . 1 1 1 1 1 1 1  =  Integer.MAX_VALUE =  2^31 - 1

取负:每一位取反,再 + 1      (two's complement)
    2  = 0000 . . . 0010
   ~2  = 1111 . . . 1101
   +1  = 1111 . . . 1110  = -2      // 同一个配方把 -2 变回 2

运算符速查表

有两组运算符长得像、脾气完全不同。位运算一次作用于全部 32 位;逻辑运算(&&、||、!)只作用于单个布尔值,而且短路求值。把它们混用是经典 bug。

一个必须先纠正的命名坑:^ 是异或(exclusive or),不是「或」——两位不同才返回 1,这个「差异检测器」正是两节之后 XOR 变成超能力的全部原因。还有面试官在听的移位细节:>> 会符号扩展(负数移完还是负数),而 >>> 永远补 0。之所以没有 <<<,是因为左移本来就在右边补 0,再来个 <<< 也和 << 一模一样。这些每一个都编译成一条硬件指令——O(1)。

位运算工具箱:set / clear / check

几乎每道位运算题都能拆成三个原语——置位、清位、读位。把它们当 one-liner 背下来,面试时就不用临场再推导。

// x 是整数,k 是位下标(0 = 最低位)
int     setBit   = x | (1 << k);          // 把第 k 位置 1
int     clearBit = x & ~(1 << k);         // 把第 k 位置 0
boolean isOne    = (x >> k & 1) != 0;      // 读第 k 位(或:(x & (1 << k)) != 0)
boolean isZero   = (x >> k & 1) == 0;      // 读第 k 位,反过来判

置第 k 位,就 OR 上一个只有第 k 位是 1 的掩码;清位就 AND 上取反的掩码;读位就把那一位移到第 0 位再掩掉其余。笔记里重点标了一个运算符优先级坑:在 Java 里 & 的优先级低于 !=,所以 x & (1 << k) != 0 会被解析成 x & ((1 << k) != 0)——这是 int & boolean 的类型错误。一定要加括号:(x & (1 << k)) != 0。就这一对漏掉的括号,是货真价实的白板 bug。

数 1 的个数:LC 191 Number of 1 Bits

LC 191 Number of 1 Bits 求 Hamming weight——有多少位是 1。解法有一条一级比一级干净的阶梯:

• 移动掩码,32 次——把掩码左移,判 (n & (mask << i)) != 0。对,但恒定 32 轮。
• 移动 n 本身,32 次——判最低位再把 n 右移。关键细节:用 >>>,不是 >>——负数在 >> 下符号扩展,你会永远循环、数出幽灵般的 1。
• 提前结束——while (n != 0) n >>>= 1,剩余位全 0 的一刻就退出。
• 最优:n &= (n - 1)——每一步抹掉最低位的 1,循环恰好跑「1 的个数」次——是 O(1 的个数),不是 O(32)。

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // 抹掉最低位的 1 —— 每个 1 只循环一次
        count++;
    }
    return count;
}

这条恒等式——n & (n - 1) 清掉最低位的 1——是整节课复用最多的技巧。减 1 会把最低位的 1 翻成 0、把它下面的 0 全翻成 1,再和原值 AND 就精准抹掉那一位。接下来两道题只是它的又一次应用。

XOR 的超能力:LC 136 Single Number

LC 136 Single Number:每个元素出现两次,只有一个出现一次,找出这个单身数。你可以排序后扫,或全塞进 HashSet——都能做,但都要额外的时间或空间。优雅解只靠一条性质:XOR 满足交换律、结合律,且 n ^ n = 0、n ^ 0 = n。把整个数组 XOR 到一起,每一对重复元素自我湮灭,只留下那个唯一值。O(n) 时间、O(1) 空间,一个数据结构都不用。

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) res ^= num;   // 成对抵消(a^a=0),单身数留下
    return res;
}

// 附加追问:a 和 b 有多少位不同?
int diff = a ^ b, bits = 0;
while (diff != 0) { diff &= (diff - 1); bits++; }   // XOR 标出差异,再 popcount

同一个「差异检测器」回答一个高频追问:两个整数 a、b 有多少位不同?算 a ^ b——每个不同的位变成 1——再用 LC 191 的 n & (n-1) 循环数这些 1。本课两个技巧,组合成一个干净答案。

2 的幂 / 4 的幂 / K 的幂(LC 231)

LC 231 Power of Two 有一整套解法,能报出好几种就是深度信号:

• 一路除——先排除 n <= 0,再 while (n % 2 == 0) n /= 2,最后判 n == 1。递归写法是同一个思路:return n > 0 && (n == 1 || (n % 2 == 0 && isPowerOfTwo(n / 2)))。
• 数比特——2 的幂恰好只有一个 1,所以它的 Hamming weight 是 1。
• 最干净那个——return n > 0 && (n & (n - 1)) == 0;清掉那唯一的 1 就得 0。又是 n & (n-1)。
• 数学炫技——因为 int 能装下的最大 2 的幂是 2^30 = 1073741824,任何 2 的幂都能整除它:return n > 0 && 1073741824 % n == 0。O(1),一次位运算都没有。

Power of Four 和 Power of K 是同套思路的推广——4 的幂要额外要求那唯一的 1 落在偶数位(或者判 Math.log(n) / Math.log(4) 是整数);一般的 k 就退回一路除的循环。

翻转比特与翻转数字(LC 190, LC 7)

LC 190 Reverse Bits 把一个 32 位整数首尾颠倒。直接做法建一个新结果:读输入的第 i 位,若是 1 就把输出的第 31 - i 位置 1。但有个更巧的原地思路——像双指针翻转数组一样。让 i 从 0 走到 15,看对称的一对 (i, 31 - i):两位已经相同就不动;不同就用 XOR 1 各翻一下。16 轮,零额外分配。

public int reverseBits(int n) {
    for (int i = 0; i < 16; i++) {          // 向中间靠拢
        int l = (n >> i) & 1;
        int r = (n >> (31 - i)) & 1;
        if (l != r) {                        // 两位不同 → 各 XOR 1 翻转
            n ^= (1 << i);
            n ^= (1 << (31 - i));
        }
    }
    return n;
}

它的十进制表亲是 LC 7 Reverse Integer:用 res = res * 10 + n % 10 剥位、n /= 10。坑在溢出——翻转后的 int 可能超过 2^31 - 1。要在乘法之前拦截:若 res > (Integer.MAX_VALUE - digit) / 10,就是马上要溢出,clamp 到 Integer.MAX_VALUE 或返回 0。翻转 String、翻转小数(12.34 → 43.21,整数部分和小数部分分别翻),都复用同一个「剥位 + 拼回」的循环。

查重与位图(LC 217 / 219 / 220)

LC 217 Contains Duplicate 和它的邻居是带拐弯的 HashSet 热身。基础版:每个元素往 set 里 add,若 add 返回 false,说明见过了——有重复。LC 219 Contains Nearby Duplicate 给间距加了约束——两个下标要在 k 以内。用一个滑动窗口 set 存最近 k 个元素:插入 nums[i] 前先踢掉 nums[i - k - 1],让 set 里永远不含距离超过 k 的元素;一次失败的 add 就是答案。(HashMap 记「值 → 最后下标」也行:遇重复时判 i - map.get(v) <= k。)LC 220 更进一步,连值的差也限制,这会把你推向 TreeSet 或分桶。

当字母表小而固定时,可以彻底丢掉 hash。对字母用 boolean[52](ASCII 用 boolean[256])标记「见过」。再推一步做成位图:把 256 个标记塞进 int[8],因为每个 int 有 32 位。对字符 c,row = c / 32 选中哪个 int、col = c % 32 选中哪一位;查用 (bitMap[row] & (1 << col)) != 0,记用 bitMap[row] |= (1 << col)。和布尔数组一样的 O(1) 成员判断,内存只用三十二分之一——这是展示「你懂 hash set 底层在干什么」的漂亮方式。

进制转换与罗马数字(LC 12 / 13)

任意进制之间的转换,都以十进制作桥梁。十进制 → b 进制:反复 % b(下一位)、/= b。b 进制 → 十进制:digit × b^i 加权求和。两步还能融合——res = res * 2 + (n % 2) 和 res = (res << 1) | (n & 1) 是一回事,一位一位地把新表示拼出来。

LC 12 Integer to Roman 靠一张查找表:预先算好个、十、百、千位对应的罗马字符串,再用 % 10 和 /= 10 剥十进制位,把每一位的数字前缀拼上。2438 → MM + CD + XXX + VIII。LC 13 Roman to Integer 反着走,用 char → 值 的 map:从右往左扫,加上每个符号的值,但当它比右边的符号小时就减去它——这一条规则就搞定所有 IV / IX / XL 的减法情形。

从零手写算术(LC 29, 69, 166, 172)

课程收尾的四道题,重新实现了语言平时白送给你的算术:

LC 29 Divide Two Integers——不用 *、/ 做除法。引擎是反复倍增:要算 a / b,就把 b 不断 << 1 翻倍,直到再翻就超过 a,减掉这一块,再对余下部分递归——每一块把它累积的倍数贡献进商。这把 O(商) 的减法循环变成 O(log 商)。两颗地雷:全程用 long,并在转换之后再取 Math.abs(让 Integer.MIN_VALUE 活下来);再特判唯一会溢出的结果 MIN_VALUE / -1,它必须 clamp 到 Integer.MAX_VALUE。

public int divide(int dividend, int divisor) {
    int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    long ans = recurDiv(a, b);
    if (ans > Integer.MAX_VALUE)               // 唯一的溢出:MIN_VALUE / -1
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    return (int) (sign * ans);
}

private long recurDiv(long a, long b) {
    if (a < b) return 0;
    long sum = b, multiple = 1;
    while ((sum << 1) <= a) { sum <<= 1; multiple <<= 1; }  // 把 b 翻倍到刚好装得下
    return multiple + recurDiv(a - sum, b);
}

LC 69 Sqrt(x)——整数平方根,在 1 … x/2+1 上二分,拿 x / mid 和 mid 比(用除法,绝不用 mid * mid,躲开溢出)。这就是 第 1 课的答案空间二分,迷你版。

LC 166 Fraction to Recurring Decimal——手算长除法。先输出整数部分,再不断把余数乘 10 再除。妙处在检测循环:把每个余数存进 HashMap,key 是它在输出里的位置;某个余数第一次重复出现,就找到了循环节,把那一段用括号括起来。符号来自两个操作数符号的一次 XOR,全程走 long 以扛住 Integer.MIN_VALUE。

LC 172 Factorial Trailing Zeroes——不用大数运算。一个末尾零来自一个 10 = 2 × 5 因子,而 5 比 2 稀有,所以答案就是 n! 里有多少个 5 的因子:n/5 + n/25 + n/125 + …。数对那个质数,就是整道题。

刷题清单