// 将x的第k位设置为1
int setBitToOne(int x, int k) { return x | (1 << k); }
// 将x的第k位设置为0
int setBitToZero(int x, int k) { return x & ~(1 << k); }
// 翻转第k位
int flipBit(int x, int k) { return x ^ (1 << k); }
// 使用异或交换两个整数
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
// 推导过程：
// a' = a ^ b
// b' = b ^ a' = b ^ (a ^ b) = a ^ (b ^ b) = a ^ 0 = a
// a'' = a' ^ b' = (a ^ b) ^ a = b
注意：当 a 和 b 指向同一内存地址时，此方法会将值置为0。实际开发中推荐使用 std::swap 或临时变量，因为现代编译器对临时变量的优化已经非常出色。
2.8 绝对值与符号判断
// 不使用分支语句的绝对值
int abs(int x) {
int mask = x >> (sizeof(int) * 8 - 1);
return (x + mask) ^ mask;
}
// 原理：当x为正数时，mask=0，返回x
// 当x为负数时，mask=-1(全1)，x+(-1)=x-1
// (x-1)^(-1) = ~(x-1) = -x = |x|
// 更简洁的写法（需避免溢出）
int abs2(int x) {
int mask = x >> 31;
return (x ^ mask) - mask;
}
// 取符号位
int sign(int x) { return x >> 31; } // 正数为0，负数为-1
// 全部异或一遍，成对的数全部消去
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int x : nums) ans ^= x;
return ans;
}
// 扩展问题：如果有两个数只出现一次，其余都出现两次？
// 思路：先全员异或得到 a^b，然后找任意一个为1的位
// 按该位将数组分成两组，各自异或消除
vector<int> singleNumber2(vector<int>& nums) {
int xorAll = 0;
for (int x : nums) xorAll ^= x;
int lb = xorAll & (-xorAll); // 最低不同位
int a = 0, b = 0;
for (int x : nums) {
if (x & lb) a ^= x;
else b ^= x;
}
return {a, b};
}
3.2 找出缺失的数
给定一个包含 [0, n] 中 n 个数的数组，找出缺失的那个数。
// 利用异或：将下标和数值全部异或
int missingNumber(vector<int>& nums) {
int n = nums.size();
int ans = n;
for (int i = 0; i < n; i++) {
ans ^= i ^ nums[i];
}
return ans;
}
// 原理：假设数组不缺数，则每个i应该等于nums[i]
// 缺失的那个数在异或过程中只出现一次（来自下标），
// 对应的数值没有出现，因此留下的就是缺失的数
3.3 找出两个不同的元素
有两个字符串 s 和 t，t 由 s 随机重排后在随机位置添加一个字符构成。找出 t 中添加的字符。
// 将两个字符串的所有字符异或，成对的消去
char findTheDifference(string s, string t) {
char ans = 0;
for (char c : s) ans ^= c;
for (char c : t) ans ^= c;
return ans;
}
// 也可以利用ASCII码的性质，一行搞定
char findDiff(string s, string t) {
return accumulate(t.begin(), t.end(), 0) -
accumulate(s.begin(), s.end(), 0);
}
3.4 数组中两数异或最大值
给定一个整数数组，找出两个数异或结果的最大值。这是Trie树与位运算结合的经典题目。
// 使用前缀树（Trie）优化，时间复杂度O(N*32)
struct TrieNode {
TrieNode* next[2] = {nullptr, nullptr};
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
TrieNode* root = new TrieNode();
// 建树：将每个数的二进制位插入Trie
for (int x : nums) {
TrieNode* p = root;
for (int i = 31; i >= 0; i--) {
int b = (x >> i) & 1;
if (!p->next[b]) p->next[b] = new TrieNode();
p = p->next[b];
}
}
// 查询：对每个数贪心地走相反位
int ans = 0;
for (int x : nums) {
TrieNode* p = root;
int cur = 0;
for (int i = 31; i >= 0; i--) {
int b = (x >> i) & 1;
if (p->next[b ^ 1]) {
cur |= (1 << i);
p = p->next[b ^ 1];
} else {
p = p->next[b];
}
}
ans = max(ans, cur);
}
return ans;
}
};
// 容斥原理求区间[1, n]中被集合S中任意数整除的数的个数
// S = {a[0], a[1], ..., a[m-1]}
int inclusionExclusion(int n, vector<int>& a) {
int m = a.size();
int ans = 0;
for (int mask = 1; mask < (1 << m); mask++) {
int lcm = 1, bits = 0;
for (int i = 0; i < m; i++) {
if (mask & (1 << i)) {
lcm = lcm / gcd(lcm, a[i]) * a[i];
// 防溢出
if (lcm > n) break;
bits++;
}
}
if (lcm > n) continue;
// 奇数个集合加，偶数个集合减
if (bits % 2 == 1) ans += n / lcm;
else ans -= n / lcm;
}
return ans;
}
六、进阶技巧与拓展
6.1 位运算实现加法
使用异或模拟无进位加法，与运算模拟进位，循环直到进位为0。
// 位运算实现整数加法
int add(int a, int b) {
while (b) {
int carry = (a & b) << 1; // 进位
a ^= b; // 无进位和
b = carry; // 循环处理进位
}
return a;
}
// 可以扩展实现减法：a - b = add(a, add(~b, 1))
// 乘法：a * b 可以通过循环加实现
int multiply(int a, int b) {
int res = 0;
while (b) {
if (b & 1) res = add(res, a);
a <<= 1;
b >>= 1;
}
return res;
}
6.2 计算整数对数
通过位运算快速计算以2为底的对数的整数部分（即最高位的位置）。
// 求floor(log2(x))，即x的最高位的位置
int floorLog2(int x) {
int res = 0;
while (x >>= 1) res++;
return res;
}
// 更快的二分查找法（32位整数）
int floorLog2Fast(uint32_t x) {
int res = 0;
if (x >= 1 << 16) { res += 16; x >>= 16; }
if (x >= 1 << 8) { res += 8; x >>= 8; }
if (x >= 1 << 4) { res += 4; x >>= 4; }
if (x >= 1 << 2) { res += 2; x >>= 2; }
if (x >= 1 << 1) { res += 1; }
return res;
}
// 向上取整到2的幂次
uint32_t roundUpToPowerOf2(uint32_t x) {
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x + 1;
}