02.8.1.3 位运算技巧
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧
02.8.1.3-001 基础位运算有哪些?优先级要注意什么?
一句话结论
位运算包括按位与 &、或 |、异或 ^、取反 ~、左移 <<、右移 >>(算术)/>>>(逻辑);位运算优先级低于算术与比较,表达式必须加括号。
概念解释
- 与:两位都 1 才 1。
- 异或:不同为 1,相同为 0。
- 移位:左移补零,右移分符号位补位。
原理流程
- 按位对齐逐位计算。
- 明确有符号/无符号口径。
- 复合表达式先加括号再写。
代码 / 示例
int a = 6 & 3; // 2
int b = 6 ^ 3; // 5
int c = 6 | 3; // 7
常见误区
- 误区:
&与逻辑&&混用;正解:&按位,&&短路逻辑。 - 误区:位运算优先级高于比较;正解:
==高于&,必须括号包裹。
追问
- Q:
>>与>>>区别? A:前者算术右移补符号位,后者逻辑右移高位补零。 - Q:取反
~作用于 int 结果? A:按 32 位补码逐位取反,结果为 -x-1。
02.8.1.3-002 n & (n-1) 有什么作用?
一句话结论
n & (n-1) 清除 n 二进制表示中最低位的 1;可用于统计 1 的个数、判断 2 的幂、观察位递减过程。
概念解释
- 最低位 1:最靠右的那个置位位。
- n-1:该位变 0,其后低位全变 1。
- 相与:保留高位,清掉最低位 1。
原理流程
- n 减 1 借位翻转最低位 1 及低位。
- 与 n 相与,最低位 1 被清。
- 重复到 0,次数即 1 的个数。
代码 / 示例
int countOnes(int n) {
int c = 0;
while (n != 0) { n &= n - 1; c++; }
return c;
}
常见误区
- 误区:该操作清掉最高位 1;正解:清的是最低位 1。
- 误区:负数也能直接用;正解:Java 负数补码下循环到 0 仍成立,但需理解补码表示。
追问
- Q:判断 2 的幂怎么写? A:
n > 0 && (n & (n-1)) == 0。 - Q:复杂度? A:O(k),k 为 1 的个数,最坏 O(log n)。
02.8.1.3-003 n & -n 得到什么?
一句话结论
n & -n 取出最低位的 1(lowbit),结果是只保留最低置位位的数;可用于定位最低位、树状数组下标运算、枚举位。
概念解释
- -n:补码 = 取反加一。
- 相与:高位抵消,留下最低位 1。
- lowbit:2^k,k 为最低位 1 所在位。
原理流程
- 对 n 取负得补码。
- 与 n 相与。
- 结果为最低位权值。
代码 / 示例
int lowbit(int n) { return n & (-n); } // 12(1100) -> 4(100)
常见误区
- 误区:lowbit 是最低位权值还是位索引;正解:得到的是权值(2^k),索引需
log2。 - 误区:n=0 时合法;正解:0 & -0 = 0,无 lowbit。
追问
- Q:树状数组哪里用它? A:
i += i & -i向上跳转,i -= i & -i向下跳转。 - Q:枚举置位位怎么做? A:
lowbit = x & -x; x -= lowbit逐个取。
02.8.1.3-004 如何判断一个数是 2 的幂?
一句话结论
大于 0 且二进制只有一个 1,即 n > 0 && (n & (n - 1)) == 0;2 的幂减一低位全 1,相与清零。
概念解释
- 2 的幂:1000... 形式。
- 单置位:n-1 与 n 无公共 1。
- 非正:0 与负数排除。
原理流程
- n <= 0 返回 false。
- 清最低位 1 后是否为 0。
- 为 0 即单置位。
代码 / 示例
boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
常见误区
- 误区:漏掉 n > 0;正解:0 也满足相与为 0,但不是 2 的幂。
- 误区:用取模 2 判断;正解:取模只能判奇偶,不能判幂。
追问
- Q:4 的幂怎么判? A:是 2 的幂且置位在偶数位,可掩码
0x55555555。 - Q:复杂度? A:O(1)。
02.8.1.3-005 统计二进制中 1 的个数有哪些写法?
一句话结论
三种:逐位检查(n >> i & 1)、清除最低位 1(n &= n-1)、内置位计数;面试常用清除法,循环次数等于 1 的个数。
概念解释
- 逐位:遍历固定位数。
- 清除法:按置位位递减。
- 内置法:语言库 popcount。
原理流程
- 选计数方式。
- 循环更新 n。
- 返回计数。
代码 / 示例
// 清除法
int hammingWeight(int n) {
int c = 0;
while (n != 0) { n &= n - 1; c++; }
return c;
}
常见误区
- 误区:对负数用逻辑/算术右移混淆;正解:Java 负数用
>>>或清除法避免死循环。 - 误区:把 0 的个数也算上;正解:只统计置位位。
追问
- Q:汉明距离是什么? A:两数异或后 1 的个数,即不同位数。
- Q:复杂度? A:清除法 O(k),逐位 O(32)。
02.8.1.3-006 异或怎么找唯一出现一次的数?
一句话结论
相同数异或为 0,0 异或 x 为 x;全部元素异或后,成对出现的数抵消,剩余即唯一出现一次的数。
概念解释
- 交换律:异或顺序无关。
- 自反:x ^ x = 0。
- 单位元:x ^ 0 = x。
原理流程
- 结果初值 0。
- 依次异或所有元素。
- 成对抵消,留下孤数。
代码 / 示例
int singleNumber(int[] nums) {
int x = 0;
for (int v : nums) x ^= v;
return x;
}
常见误区
- 误区:只适用于全是偶数次出现;正解:其余数成对(偶数次)出现,孤数一次。
- 误区:用哈希表统计才算最优;正解:异或 O(1) 空间。
追问
- Q:两个数各出现一次怎么办? A:按 lowbit 分组,两组内分别异或。
- Q:三次出现的数能用异或吗? A:不能直接抵消,需位计数或状态机。
02.8.1.3-007 两个只出现一次的数怎么分组异或?
一句话结论
全部异或得到两孤数异或值;取其 lowbit 作为分组位,按该位是否为 1 把数组分两组,每组内只含一个孤数,分别异或得到两数。
概念解释
- 异或值:两孤数不同位的掩码。
- lowbit:某个不同位,保证两数落不同组。
- 分组后:每组内其余数成对抵消。
原理流程
- 全员异或得 diff。
- mask = diff & -diff。
- 按 mask 分组,组内异或得 a、b。
代码 / 示例
int diff = 0; for (int v : nums) diff ^= v;
int mask = diff & -diff;
int a = 0, b = 0;
for (int v : nums) { if ((v & mask) == 0) a ^= v; else b ^= v; }
常见误区
- 误区:分组位任选;正解:必须来自 diff 的置位位,保证两孤数分开。
- 误区:同组成对数未抵消;正解:成对数值相同,自然同组抵消。
追问
- Q:复杂度? A:O(n) 时间,O(1) 空间。
- Q:三个孤数能这么做吗? A:不能,分组不足以分离三个目标。
02.8.1.3-008 不用临时变量能交换两个数吗?
一句话结论
可用异或交换:a ^= b; b ^= a; a ^= b;;但数组下标场景需防自交换,工程上一般直接用临时变量,异或交换主要考查理解。
概念解释
- 三步异或:利用自反性还原原值。
- 自交换风险:同一位置交换会清零。
- 可读性:临时变量更清晰。
原理流程
- a = a ^ b。
- b = b ^ a 得原 a。
- a = a ^ b 得原 b。
代码 / 示例
a ^= b; b ^= a; a ^= b; // 仅在 a、b 为不同存储位置时使用
常见误区
- 误区:数组 i、j 相等时也执行;正解:先判断 i != j,否则该位置被清零。
- 误区:异或交换比临时变量快;正解:现代编译器优化后无优势,可读性优先。
追问
- Q:加减交换有什么风险? A:整数溢出,异或无此问题。
- Q:面试为什么还考它? A:检验异或性质理解,非工程推荐写法。
02.8.1.3-009 移位做乘除 2 的幂要注意什么?
一句话结论
左移 k 位等价乘 2^k,右移 k 位对非负数等价整除 2^k;Java 负数算术右移向负无穷取整,且移位结果可能溢出,乘除优先用算术运算符。
概念解释
- 左移:低位补零。
- 算术右移:高位补符号位。
- 溢出:移位超 int/long 范围截断。
原理流程
- 判断操作数符号与范围。
- 移位等价换算。
- 边界检查防溢出。
代码 / 示例
int half = n >> 1; // 非负整数除以 2
int double_ = n << 1; // 乘 2,注意溢出
常见误区
- 误区:负数右移与 trunc 整除一致;正解:Java
>>向负无穷取整,/2向零取整。 - 误区:移位位数取模未考虑;正解:移位位数按类型位宽取模,超大位数结果非直觉。
追问
- Q:求中位点防溢出怎么写? A:
l + (r - l) / 2,不用(l+r)/2。 - Q:
>>>0作用? A:把 int 按无符号看待。
02.8.1.3-010 不用加减运算符怎么做两数相加?
一句话结论
用半加器思路:异或得无进位和,与左移一位得进位;进位非零时递归/迭代把进位加回,直到进位为零;Java 用循环避免递归深度。
概念解释
- 无进位和:a ^ b。
- 进位位:(a & b) << 1。
- 迭代:把进位并入新一轮。
原理流程
- sum = a ^ b,carry = (a & b) << 1。
- a = sum,b = carry。
- b == 0 返回 a。
代码 / 示例
int add(int a, int b) {
while (b != 0) {
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum; b = carry;
}
return a;
}
常见误区
- 误区:进位不左移;正解:进位属于高位,需 <<1。
- 误区:一次异或就是结果;正解:必须迭代消掉进位。
追问
- Q:复杂度? A:进位位数有限,O(log 数值位)。
- Q:支持负数吗? A:补码表示下天然支持。
02.8.1.3-011 位掩码怎么表示集合?
一句话结论
用整数每个二进制位代表一个元素是否在集合中:位为 1 表示在;交并差补分别对应 &、|、& ~、^;n <= 32 用 int,n <= 64 用 long。
概念解释
- 成员位:第 i 位对应元素 i。
- 集合运算:按位逻辑运算。
- 规模上限:掩码位数约束 n。
原理流程
- 元素编号 0~n-1。
- 置位加入,清位移除。
- 位运算做集合交并差。
代码 / 示例
int set = 0;
set |= 1 << i; // 加入
set &= ~(1 << i); // 移除
boolean has = (set & (1 << i)) != 0;
int inter = a & b, union = a | b;
常见误区
- 误区:n > 32 仍用 int;正解:超 32 需 long 或位图/集合类。
- 误区:位号与元素值混用;正解:元素先映射到 0 起的连续索引。
追问
- Q:状态压缩 DP 用什么? A:掩码表示集合状态,见 02.7.2.3。
- Q:空集怎么表示? A:0。
02.8.1.3-012 如何枚举一个集合的所有子集?
一句话结论
掩码从 0 到 2^n-1 枚举,每个掩码对应一个子集;按位判断成员是否在掩码中;时间 O(2^n · n),仅适用于 n 较小的场景。
概念解释
- 2^n 个子集:每位选或不选。
- 成员判断:
mask & (1 << i)。 - 规模限制:指数级。
原理流程
- mask 从 0 递增到 (1<<n)-1。
- 逐位收集成员。
- 处理该子集。
代码 / 示例
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) != 0) { /* 选中元素 i */ }
}
常见误区
- 误区:n=20 仍枚举全部子集;正解:2^20 已约百万,n 再大需剪枝或 DP。
- 误区:掩码与子集大小混淆;正解:掩码是成员集合,大小用 popcount 求。
追问
- Q:枚举真子集? A:跳过 mask = 全集。
- Q:复杂度? A:O(2^n · n),空间 O(n)。
02.8.1.3-013 位运算怎么做奇偶判断与取末位?
一句话结论
n & 1 为 1 是奇数,为 0 是偶数;末位数字/比特由最低位给出;比取模更直观,但可读性上 % 2 同样常用。
概念解释
- 最低位:奇偶由末位决定。
- 与 1 掩码:保留最低位。
- 等价:n & 1 == n % 2(非负)。
原理流程
- 与 1 相与。
- 结果 1 奇,0 偶。
- 取末位比特同理。
代码 / 示例
boolean odd = (n & 1) == 1;
常见误区
- 误区:负数用
%2与&1结果表述不同;正解:&1给末位,负奇偶判定仍可用。 - 误区:
&1优先级低于==;正解:加括号。
追问
- Q:取末位数字怎么做? A:
n % 10,不是位运算。 - Q:判断位是否为 1 通用写法? A:
(x >> i) & 1。
02.8.1.3-014 二进制位翻转/颠倒怎么做?
一句话结论
逐位交换对称位置比特:左右指针从两端向中间,不同则翻转对应位;或查表按字节反转;颠倒 32 位需明确高位低位口径。
概念解释
- 对称位:第 i 位与第 31-i 位。
- 翻转:两值不同才交换。
- 查表:字节级预计算反转表。
原理流程
- 定位对称位。
- 比较并通过异或翻转。
- 向中间收敛。
代码 / 示例
// 异或翻转两位:x ^= (1<<i) ^ (1<<j)
常见误区
- 误区:直接整体取反
~;正解:颠倒位是重排,不是逐位取反。 - 误区:位宽搞错;正解:明确 int 32 位或指定位数。
追问
- Q:颠倒字节序用于什么? A:大小端转换。
- Q:复杂度? A:逐位 O(log n),查表 O(1)。
02.8.1.3-015 求平均值如何避免溢出?
一句话结论
不用 (a + b) / 2(和可能溢出),改用 a + (b - a) / 2;二分查找取下中位防溢出;移位写法同样需先保证范围。
概念解释
- 溢出:两正数和超 int 上限变负。
- 差值:b-a 范围更小。
- 等价:a + (b-a)/2 = (a+b)/2(向下取整)。
原理流程
- 取较小值 a。
- 加差值一半。
- 避免直接求和。
代码 / 示例
int mid = l + (r - l) / 2; // 二分防溢出
int avg = a + (b - a) / 2;
常见误区
- 误区:认为 int 范围足够不加防护;正解:边界附近求和仍可能溢出。
- 误区:
(a + b) >>> 1不可用;正解:无符号平均可用>>>1,但差值法更通用。
追问
- Q:二分中位选偏左还是偏右? A:
l+(r-l)/2偏左,配合区间收缩模板。 - Q:long 还会溢出吗? A:超大范围仍需评估,按类型上限判断。
02.8.1.3-016 状态位的置位、清位、取反、判断怎么写?
一句话结论
置位 s |= 1<<i;清位 s &= ~(1<<i);取反 s ^= 1<<i;判断 (s & (1<<i)) != 0;掩码位号必须在类型位宽内。
概念解释
- 置位:位变 1。
- 清位:位变 0。
- 判断:位是否为 1。
原理流程
- 生成掩码
1 << i。 - 按操作选位运算。
- 回写状态。
代码 / 示例
s |= 1 << i; // 置位
s &= ~(1 << i); // 清位
s ^= 1 << i; // 取反
boolean on = (s & (1 << i)) != 0;
常见误区
- 误区:清位写成
s &= (1<<i);正解:要取反掩码~(1<<i)。 - 误区:
1 << i中 i 超位宽;正解:i < 32(int)/64(long)。
追问
- Q:批量置位? A:掩码或入状态。
- Q:状态位综合在哪些题? A:状压 DP、标记冲突、权限位。
02.8.1.3-017 格雷码是什么?怎么生成?
一句话结论
格雷码相邻两个数只有一位不同;n 位格雷码可由二进制码右移一位异或得到:gray = i ^ (i >> 1);用于减少位翻转次数。
概念解释
- 相邻一位差:环形排列中过渡平滑。
- 编码映射:二进制转格雷。
- 应用:位翻转最小化、卡诺图。
原理流程
- 对序号 i 取
i ^ (i >> 1)。 - 按序输出即为格雷码序列。
- 相邻验证仅一位变化。
代码 / 示例
int gray(int i) { return i ^ (i >> 1); }
常见误区
- 误区:格雷码就是二进制逆序;正解:是相邻一位差的编码映射。
- 误区:生成需要递归回溯;正解:公式法 O(1) 每项。
追问
- Q:格雷码怎么转回二进制? A:逐位前缀异或还原。
- Q:为什么相邻一位差? A:高位相同部分抵消,低位变化被异或结构约束。
02.8.1.3-018 位运算能替代哪些乘除?
一句话结论
乘除 2 的幂可用移位替代:x << k 乘 2^k,x >> k 整除 2^k(非负);编译器通常已自动做此优化,手写移位主要用于掩码、状态位等位场景。
概念解释
- 2 的幂:二进制移位。
- 非 2 的幂:不能用移位。
- 编译优化:现代编译器识别常量乘除。
原理流程
- 判断乘数是否 2 的幂。
- 是则移位换算。
- 注意溢出与符号。
代码 / 示例
int x4 = x << 2; // *4
int x8 = x >> 3; // /8(非负)
常见误区
- 误区:任意乘法都拆移位;正解:非 2 幂需加减组合,可读性差且未必更快。
- 误区:负数右移等价除法;正解:向负无穷取整,与除 2 向零取整不同。
追问
- Q:乘 3 能移位吗? A:
(x<<1)+x,但不推荐手写。 - Q:移位优化有必要手动做吗? A:一般交给编译器,位运算场景除外。
02.8.1.3-019 位运算有哪些常见陷阱?
一句话结论
陷阱:运算符优先级(比较高于 &)、符号位与算术右移、移位位数超位宽、整数溢出、~ 补码结果、负数补码表示;写表达式加括号并核对符号口径。
概念解释
- 优先级:
&低于==。 - 符号:有符号数高位含义。
- 溢出:位运算结果截断。
原理流程
- 表达式加括号。
- 确认操作数符号与位宽。
- 边界用例核对结果。
代码 / 图示
优先级:比较 > 按位与;右移:>> 补符号位,>>> 补零
常见误区
- 误区:
if (a & b == 0)写法正确;正解:需if ((a & b) == 0)。 - 误区:移位位数可以任意大;正解:按位宽取模,行为需查语言规范。
追问
- Q:
~0等于多少? A:-1(全 1 补码)。 - Q:位运算调试看什么? A:转二进制对照每一位变化。
02.8.1.3-020 比特位计数(LC 338)怎么用位运算做?
一句话结论
求 0~n 每个数的 1 的个数;递推:dp[i] = dp[i >> 1] + (i & 1)(高位子问题 + 最低位),或 dp[i] = dp[i & (i-1)] + 1(清除最低位 1 加一);O(n) 线性打表。
概念解释
- 子问题:去掉最低位或最低位 1 后的数。
- 递推:已知子问题答案加一位贡献。
- 打表:一次遍历得全部结果。
原理流程
- dp[0] = 0。
- 按递推式填表。
- 返回数组。
代码 / 示例
int[] countBits(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++)
dp[i] = dp[i & (i - 1)] + 1;
return dp;
}
常见误区
- 误区:每个数单独 popcount;正解:递推复用子问题,O(n)。
- 误区:递推式漏加最低位贡献;正解:
+ (i & 1)或清除法 +1。
追问
- Q:复杂度? A:O(n) 时间,O(n) 结果空间。
- Q:与 02.7.1.1 DP 关系? A:典型线性递推,状态为数值,转移靠位运算。