算法实战：位运算解法详解
35. 两个整数之和
题目描述
不使用运算符 + 和 -，计算两整数 a、b 之和。
解题思路
位运算的核心在于模拟加法器的逻辑。异或 ^ 运算本质上是无进位加法，而按位与 & 操作能得到需要进位的位置。由于进位需要向左移动一位才能加到正确位置，因此我们需要循环处理，直到进位变为 0。
C++ 实现
class Solution {
public:
int getSum(int a, int b) {
// 当进位不为 0 时继续循环
while (b != 0) {
int x = a ^ b; // 无进位相加
int y = (a & b) << 1; // 计算进位并左移
a = x;
b = y;
}
return a;
}
};
流程解析
36. 只出现一次的数字 II
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
解题思路
统计所有数字在每一个二进制位上的总和。因为其他数字都出现了三次，所以除目标数字外，每一位的累加和都能被 3 整除。对每一位的累加和取模 3，即可还原出目标数字的二进制表示。
C++ 实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = ;
( i = ; i < ; i++) {
sum = ;
( x : nums) {
sum += ((x >> i) & );
}
ret |= ((sum % ) << i);
}
ret;
}
};
