如果面试官说“请写一个函数计算a b但不许用和-。”多数人的第一反应是“这不可能”。但拆开加法这件事它其实由两个彼此独立的部件组成无进位和两位不同则为1、相同则为0 —— 这不就是异或吗进位只有两位都为1才产生进位且要左移一位 —— 这是与左移。于是加法被翻译成a b (a ^ b) ((a b) 1)右边还剩一个没关系——把它当成“下一轮的a和b”反复迭代直到进位为0。因为每轮进位至少左移一位最多32轮必然收敛。这就是LC.371的全部。它的价值不在于“比快”实测反而慢16倍而在于它逼你理解算术运算并不是原子的它们是位运算的组合。 题目速览30秒读懂题目1两整数之和LC.371不使用和-计算a b。示例1 2 32 3 5-1 1 0题目2颠倒二进制位LC.190延伸颠倒给定的32位无符号整数的二进制位。示例43261596→964176192题目3两数相除LC.29延伸不使用乘法、除法和mod返回商向零截断。示例10 / 3 37 / -3 -2 核心思路加法的两个半部件设a、b在第k位上的比特分别为aₖ、bₖ来自低位的进位为cₖ。那么该位的结果暂不考虑向高位进位aₖ ^ bₖ ^ cₖ该位产生的进位至少两位为1时为1即(aₖ bₖ) | (cₖ (aₖ ^ bₖ))如果我们把“低位进位”单独拎出来作为下一轮处理就可以写成两步部件位运算含义无进位和a ^ b两位不同才为1不产生进位进位(a b) 1两位都为1 才进位且进到高一位然后新的a a ^ b 本轮的无进位和 新的b (a b) 1 本轮的进位整体左移一位 重复直到b 0 没有进位了a就是答案为什么一定收敛进位每轮至少左移一位。在32位定长整数里最多左移32次就全部溢出消失所以循环必然终止。这个“每步砍掉一个二进制位”的结构和快排、快速选择共享同一种思想——减治decrease-and-conquer。⚠️ Python独有的一坑整数无限位上面的收敛性论证依赖“整数是32位定长”。而Python的整数是任意精度的负数的左移会无限延伸b永远不为0死循环。标准解法是手动模拟32位MASK0xFFFFFFFF# 低32位全1# 运算时把中间结果 MASK 截断到32位# 输出时若最高位为 1即 0x80000000说明是负数还原为Python负数还原负数的技巧是~(a ^ MASK)把32位表示按位取反后Python会把它解释成对应的负数值。这是本系列到目前为止两个语言差异最大的一处必须讲清楚。LC.29倍增减法除法不许用/、*、%那就回到除法的定义商是“能减多少次”。逐次减1个除数太慢2147483647 / 1要减21亿次。优化思路是倍增从最大的2^31开始往下试若dividend divisor i就减掉divisor i并给商加上1 i。本质是把商写成二进制逐位确定——和快速幂是同一个“按二进制位展开”的套路。LC.190分治交换逐位移位是O(32)。更漂亮的是分治交换先交换相邻的1位再交换相邻的 位块再4位、8位、16位——5步完成n ((n 0x55555555) 1) | ((n 1) 0x55555555) # 奇偶位交换 n ((n 0x33333333) 2) | ((n 2) 0x33333333) # 每2位一组交换 n ((n 0x0F0F0F0F) 4) | ((n 4) 0x0F0F0F0F) # 每4位 n ((n 0x00FF00FF) 8) | ((n 8) 0x00FF00FF) # 每8位 n ((n 0x0000FFFF) 16) | ((n 16) 0x0000FFFF) # 每16位掩码0x55555555 0101...取出所有奇数位0x33333333 00110011...取出每 2 位块的低半部分。这是分治思想在位级别的最小样本。️ 图解算法手把手走一遍加法迭代a 9 (1001)、b 5 (0101)答案14轮次a无进位和b进位说明初始1001(9)0101(5)原始输入11100(12)0010(2)9^5 12(95)1 (0001)1 221110(14)0000(0)12^2 14(122)1 0结束140进位为0a即答案逐位核对第一轮a 1 0 0 1 b 0 1 0 1 ───────────── a^b 1 1 0 0 ← 无进位和 ab 0 0 0 1 ← 只有第0位都是1 1 0 0 1 0 ← 进位左移到第1位LC.29 倍增减法100 / 3商应为33i3 i剩余被除数是否可减操作累计商596100✅减96 → 剩4100000 324484❌跳过323244❌跳过322124❌跳过32164❌跳过32034✅减3 → 剩110000133最终商33余数1 ✓。商33 100001₂正是每次成功减法置位的累积结果。 代码实现Python JavaPython版classSolution:MASK0xFFFFFFFF# 32位全1MAX_INT0x7FFFFFFF# 32位有符号整数最大值# ---------- LC.371 两整数之和 ----------defgetSum(self,a:int,b:int)-int:aself.MASK bself.MASKwhileb!0:a,b(a^b)self.MASK,((ab)1)self.MASKreturnaifaself.MAX_INTelse~(a^self.MASK)# ---------- LC.190 颠倒二进制位 ----------defreverseBits(self,n:int)-int:n((n0x55555555)1)|((n1)0x55555555)n((n0x33333333)2)|((n2)0x33333333)n((n0x0F0F0F0F)4)|((n4)0x0F0F0F0F)n((n0x00FF00FF)8)|((n8)0x00FF00FF)return((n0x0000FFFF)16)|((n16)0x0000FFFF)# ---------- LC.29 两数相除 ----------defdivide(self,dividend:int,divisor:int)-int:INT_MAX,INT_MIN2**31-1,-2**31ifdividendINT_MINanddivisor-1:returnINT_MAX sign-1if(dividend0)^(divisor0)else1a,babs(dividend),abs(divisor)quotient0foriinrange(31,-1,-1):ifa(bi):a-bi quotient|1ireturnquotientifsign1else-quotientJava版classSolution{//---------- LC.371 两整数之和 ----------publicintgetSum(inta,intb){// Java的int本身就是32位定长进位溢出后自然归零while(b!0){intcarry(ab)1;aa^b;bcarry;}returna;}//---------- LC.190 颠倒二进制位 ----------publicintreverseBits(intn){n((n0x55555555)1)|((n1)0x55555555);n((n0x33333333)2)|((n2)0x33333333);n((n0x0F0F0F0F)4)|((n4)0x0F0F0F0F);n((n0x00FF00FF)8)|((n8)0x00FF00FF);return((n0x0000FFFF)16)|((n16)0x0000FFFF);}//---------- LC.29 两数相除 ----------publicintdivide(intdividend,intdivisor){if(dividendInteger.MIN_VALUEdivisor-1)returnInteger.MAX_VALUE;intsign((dividend0)^(divisor0))?-1:1;longaMath.abs((long)dividend),bMath.abs((long)divisor);longquotient0;for(inti31;i0;i--){if(a(bi)){a-bi;quotient|1Li;}}return(int)(sign1?quotient:-quotient);}}⚠️防坑提醒必看Python必须手动截32位否则负数左移死循环。LC.29唯一溢出场景INT_MIN / -1题目约定返回INT_MAX。LC.190的Java必须用逻辑右移对负数会补符号位。⏱️ 复杂度分析面试必问题目解法时间空间LC.371位运算迭代O(1)最多32轮O(1)LC.190逐位移位O(32) O(1)O(1)LC.190分治交换O(log32) O(5)O(1)LC.29逐次减法O(商)O(1)LC.29倍增减法O(logn)32轮O(1)实测位运算加法比a b快吗不。10万次加法写法耗时相对直接a b0.003s1×位运算迭代0.051s16.6×慢必须如实说明LC.371是原理题不是性能题。真实代码里永远应该写a b——CPU有专门的加法指令你用32轮循环去模拟它慢一个数量级是必然的。这道题考的是“你能不能把加法拆开”不是“你能不能写得更快”。那LC.29的倍增减法呢这里位运算是真赢场景倍增减法逐次减法差距1,000,000 / 30.000002s0.017s8882×100,000,000 / 70.000002s0.694s32万×按10^8 / 7实测0.69s 线性外推2147483647 / 1用逐次减法需要约100秒——彻底不可用。倍增把O(商) 压成O(log商)这才是位运算该去的地方。 举一反三6道高频变体题题号题目与本题的关系LC.190颠倒二进制位分治交换5步O(1)LC.29两数相除倍增减法LC.369加一位运算做加法的简化版LC.67二进制求和字符串版同样是“进位迭代”LC.338比特位计数位n (n-1)LC.371两整数之和本题 面试追问模拟提前准备惊艳全场Q1进位为什么一定归零每轮进位都要左移一位。在32位定长整数里左移32次后所有比特都被移出进位变成0。所以循环上界是32轮复杂度O(1)。Python里因为整数无限位必须手动 MASK才能复现这个性质。Q2减法怎么用位运算做a - b a (~b 1)即“加上b的补码”。而~b 1本身又要用位运算加法实现。本质上减法没有独立的位运算部件它是加法的衍生。Q3乘法呢移位 加法。把乘数写成二进制逐位判断该位为1就加上“被乘数左移相应位”。这与倍增减法除法恰好对偶——一个在累加一个在累减都是“按二进制位展开”的减治。Q4分治交换的掩码为什么是0x555555550x55 0101 0101即“奇数位为1、偶数位为0”。用它相与就取出所有奇数位左移1位后正好落到偶数位上同时原数右移1位后再与它相与得到原来的偶数位。两者或起来就完成了奇偶位的交换。 实战小技巧刷题党必备口诀加法 异或无进位和 与左移进位循环到进位归零。模板Python记得 MASK截32位并还原负数除法用倍增减法。防坑LC.29处理INT_MIN / -1LC.190Java用。 实际应用场景不止是刷题底层与大数运算任意精度整数库内部用位运算组合出加减乘除硬件描述ALU加法器电路本身就是“异或门 与门 移位”密码学与哈希位混合是哈希函数的核心短链ID混淆溢出敏感场景网络协议、文件格式中手动控制32位语义 今日思考题实测显示位运算加法比a b慢16.6倍但倍增减法比逐次减法快32万倍。同样是位运算为什么一个慢一个快提示看它替代的是什么——是CPU已有指令的操作还是原本要跑O(n)次循环的操作。