企业官网建设流程全解析

如果面试官说：“请写一个函数计算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 = 3；2 + 3 = 5；-1 + 1 = 0

题目2：颠倒二进制位（LC.190，延伸）

颠倒给定的32位无符号整数的二进制位。

示例：43261596→964176192

题目3：两数相除（LC.29，延伸）

不使用乘法、除法和mod，返回商（向零截断）。

示例：10 / 3 = 3；7 / -3 = -2

🧠 核心思路：加法的两个半部件

设a、b在第k位上的比特分别为aₖ、bₖ，来自低位的进位为cₖ。那么：

• 该位的结果（暂不考虑向高位进位）：aₖ ^ bₖ ^ cₖ
• 该位产生的进位：至少两位为1时为1，即(aₖ & bₖ) | (cₖ & (aₖ ^ bₖ))

如果我们把“低位进位”单独拎出来作为下一轮处理，就可以写成两步：

然后：

新的a = a ^ b （本轮的无进位和） 新的b = (a & b) << 1 （本轮的进位，整体左移一位） 重复，直到b == 0 （没有进位了，a就是答案）

为什么一定收敛？
进位每轮至少左移一位。在32位定长整数里，最多左移32次就全部溢出消失，所以循环必然终止。
这个“每步砍掉一个二进制位”的结构，和快排、快速选择共享同一种思想——减治（decrease-and-conquer）。

⚠️ Python独有的一坑：整数无限位

上面的收敛性论证依赖“整数是32位定长”。而Python的整数是任意精度的：负数的左移会无限延伸，b永远不为0，死循环。

标准解法是手动模拟32位：

MASK=0xFFFFFFFF# 低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 = 1 0 0 1 b = 0 1 0 1 ───────────── a^b = 1 1 0 0 ← 无进位和 a&b = 0 0 0 1 ← 只有第0位都是1 <<1 = 0 0 1 0 ← 进位左移到第1位

LC.29 倍增减法：100 / 3，商应为33

最终商33，余数1 ✓。商33 =100001₂，正是每次成功减法置位的累积结果。

💻 代码实现（Python + Java）

Python版

classSolution:MASK=0xFFFFFFFF# 32位全1MAX_INT=0x7FFFFFFF# 32位有符号整数最大值# ---------- LC.371 两整数之和 ----------defgetSum(self,a:int,b:int)->int:a&=self.MASK b&=self.MASKwhileb!=0:a,b=(a^b)&self.MASK,((a&b)<<1)&self.MASKreturnaifa<=self.MAX_INTelse~(a^self.MASK)# ---------- LC.190 颠倒二进制位 ----------defreverseBits(self,n:int)->int:n=((n&0x55555555)<<1)|((n>>1)&0x55555555)n=((n&0x33333333)<<2)|((n>>2)&0x33333333)n=((n&0x0F0F0F0F)<<4)|((n>>4)&0x0F0F0F0F)n=((n&0x00FF00FF)<<8)|((n>>8)&0x00FF00FF)return((n&0x0000FFFF)<<16)|((n>>16)&0x0000FFFF)# ---------- LC.29 两数相除 ----------defdivide(self,dividend:int,divisor:int)->int:INT_MAX,INT_MIN=2**31-1,-2**31ifdividend==INT_MINanddivisor==-1:returnINT_MAX sign=-1if(dividend<0)^(divisor<0)else1a,b=abs(dividend),abs(divisor)quotient=0foriinrange(31,-1,-1):ifa>=(b<<i):a-=b<<i quotient|=1<<ireturnquotientifsign==1else-quotient

Java版

classSolution{//---------- LC.371 两整数之和 ----------publicintgetSum(inta,intb){// Java的int本身就是32位定长，进位溢出后自然归零while(b!=0){intcarry=(a&b)<<1;a=a^b;b=carry;}returna;}//---------- LC.190 颠倒二进制位 ----------publicintreverseBits(intn){n=((n&0x55555555)<<1)|((n>>>1)&0x55555555);n=((n&0x33333333)<<2)|((n>>>2)&0x33333333);n=((n&0x0F0F0F0F)<<4)|((n>>>4)&0x0F0F0F0F);n=((n&0x00FF00FF)<<8)|((n>>>8)&0x00FF00FF);return((n&0x0000FFFF)<<16)|((n>>>16)&0x0000FFFF);}//---------- LC.29 两数相除 ----------publicintdivide(intdividend,intdivisor){if(dividend==Integer.MIN_VALUE&&divisor==-1)returnInteger.MAX_VALUE;intsign=((dividend<0)^(divisor<0))?-1:1;longa=Math.abs((long)dividend),b=Math.abs((long)divisor);longquotient=0;for(inti=31;i>=0;i--){if(a>=(b<<i)){a-=b<<i;quotient|=1L<<i;}}return(int)(sign==1?quotient:-quotient);}}

⚠️防坑提醒（必看）：

• Python必须手动截32位，否则负数左移死循环。
• LC.29唯一溢出场景INT_MIN / -1，题目约定返回INT_MAX。
• LC.190的Java必须用>>>（逻辑右移），>>对负数会补符号位。

⏱️ 复杂度分析（面试必问）

实测：位运算加法比a + b快吗？

不。10万次加法：

必须如实说明：LC.371是原理题，不是性能题。
真实代码里永远应该写a + b——CPU有专门的加法指令，你用32轮循环去模拟它，慢一个数量级是必然的。这道题考的是“你能不能把加法拆开”，不是“你能不能写得更快”。

那LC.29的倍增减法呢？这里位运算是真赢：

按10^8 / 7实测0.69s 线性外推，2147483647 / 1用逐次减法需要约100秒——彻底不可用。倍增把O(商) 压成O(log商)，这才是位运算该去的地方。

🚀 举一反三：6道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：进位为什么一定归零？

每轮进位都要左移一位。在32位定长整数里，左移32次后所有比特都被移出，进位变成0。
所以循环上界是32轮，复杂度O(1)。Python里因为整数无限位，必须手动& MASK才能复现这个性质。

Q2：减法怎么用位运算做？

a - b = a + (~b + 1)，即“加上b的补码”。
而~b + 1本身又要用位运算加法实现。本质上减法没有独立的位运算部件，它是加法的衍生。

Q3：乘法呢？

移位 + 加法。把乘数写成二进制，逐位判断：该位为1就加上“被乘数左移相应位”。
这与倍增减法（除法）恰好对偶——一个在累加，一个在累减，都是“按二进制位展开”的减治。

Q4：分治交换的掩码为什么是0x55555555？

0x55 = 0101 0101，即“奇数位为1、偶数位为0”。
用它相与就取出所有奇数位，左移1位后正好落到偶数位上；
同时原数右移1位后再与它相与，得到原来的偶数位。两者或起来，就完成了奇偶位的交换。

🧩 实战小技巧（刷题党必备）

• 口诀：加法 = 异或（无进位和）+ 与左移（进位），循环到进位归零。
• 模板：Python记得& MASK截32位并还原负数；除法用倍增减法。
• 防坑：LC.29处理INT_MIN / -1；LC.190Java用>>>。

📈 实际应用场景（不止是刷题）

• 底层与大数运算：任意精度整数库内部用位运算组合出加减乘除
• 硬件描述：ALU加法器电路本身就是“异或门 + 与门 + 移位”
• 密码学与哈希：位混合是哈希函数的核心（短链ID混淆）
• 溢出敏感场景：网络协议、文件格式中手动控制32位语义

🎁 今日思考题

实测显示位运算加法比a + b慢16.6倍，但倍增减法比逐次减法快32万倍。
同样是位运算，为什么一个慢一个快？
提示：看它替代的是什么——是CPU已有指令的操作，还是原本要跑O(n)次循环的操作。