罗罗编程学习记录
本页内容 展开查看

02.8.1.3 位运算技巧

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧

02.8.1.3-001 基础位运算有哪些?优先级要注意什么?

一句话结论

位运算包括按位与 &、或 |、异或 ^、取反 ~、左移 <<、右移 >>(算术)/>>>(逻辑);位运算优先级低于算术与比较,表达式必须加括号。

概念解释

  • 与:两位都 1 才 1。
  • 异或:不同为 1,相同为 0。
  • 移位:左移补零,右移分符号位补位。

原理流程

  1. 按位对齐逐位计算。
  2. 明确有符号/无符号口径。
  3. 复合表达式先加括号再写。

代码 / 示例

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。

原理流程

  1. n 减 1 借位翻转最低位 1 及低位。
  2. 与 n 相与,最低位 1 被清。
  3. 重复到 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 所在位。

原理流程

  1. 对 n 取负得补码。
  2. 与 n 相与。
  3. 结果为最低位权值。

代码 / 示例

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 与负数排除。

原理流程

  1. n <= 0 返回 false。
  2. 清最低位 1 后是否为 0。
  3. 为 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。

原理流程

  1. 选计数方式。
  2. 循环更新 n。
  3. 返回计数。

代码 / 示例

// 清除法
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。

原理流程

  1. 结果初值 0。
  2. 依次异或所有元素。
  3. 成对抵消,留下孤数。

代码 / 示例

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:某个不同位,保证两数落不同组。
  • 分组后:每组内其余数成对抵消。

原理流程

  1. 全员异或得 diff。
  2. mask = diff & -diff。
  3. 按 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;;但数组下标场景需防自交换,工程上一般直接用临时变量,异或交换主要考查理解。

概念解释

  • 三步异或:利用自反性还原原值。
  • 自交换风险:同一位置交换会清零。
  • 可读性:临时变量更清晰。

原理流程

  1. a = a ^ b。
  2. b = b ^ a 得原 a。
  3. 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 范围截断。

原理流程

  1. 判断操作数符号与范围。
  2. 移位等价换算。
  3. 边界检查防溢出。

代码 / 示例

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。
  • 迭代:把进位并入新一轮。

原理流程

  1. sum = a ^ b,carry = (a & b) << 1。
  2. a = sum,b = carry。
  3. 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。

原理流程

  1. 元素编号 0~n-1。
  2. 置位加入,清位移除。
  3. 位运算做集合交并差。

代码 / 示例

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)。
  • 规模限制:指数级。

原理流程

  1. mask 从 0 递增到 (1<<n)-1。
  2. 逐位收集成员。
  3. 处理该子集。

代码 / 示例

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 相与。
  2. 结果 1 奇,0 偶。
  3. 取末位比特同理。

代码 / 示例

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 位。
  • 翻转:两值不同才交换。
  • 查表:字节级预计算反转表。

原理流程

  1. 定位对称位。
  2. 比较并通过异或翻转。
  3. 向中间收敛。

代码 / 示例

// 异或翻转两位: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(向下取整)。

原理流程

  1. 取较小值 a。
  2. 加差值一半。
  3. 避免直接求和。

代码 / 示例

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. 生成掩码 1 << i。
  2. 按操作选位运算。
  3. 回写状态。

代码 / 示例

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);用于减少位翻转次数。

概念解释

  • 相邻一位差:环形排列中过渡平滑。
  • 编码映射:二进制转格雷。
  • 应用:位翻转最小化、卡诺图。

原理流程

  1. 对序号 i 取 i ^ (i >> 1)。
  2. 按序输出即为格雷码序列。
  3. 相邻验证仅一位变化。

代码 / 示例

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 的幂:不能用移位。
  • 编译优化:现代编译器识别常量乘除。

原理流程

  1. 判断乘数是否 2 的幂。
  2. 是则移位换算。
  3. 注意溢出与符号。

代码 / 示例

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 位运算有哪些常见陷阱?

一句话结论

陷阱:运算符优先级(比较高于 &)、符号位与算术右移、移位位数超位宽、整数溢出、~ 补码结果、负数补码表示;写表达式加括号并核对符号口径。

概念解释

  • 优先级:& 低于 ==。
  • 符号:有符号数高位含义。
  • 溢出:位运算结果截断。

原理流程

  1. 表达式加括号。
  2. 确认操作数符号与位宽。
  3. 边界用例核对结果。

代码 / 图示

优先级:比较 > 按位与;右移:>> 补符号位,>>> 补零

常见误区

  • 误区: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 后的数。
  • 递推:已知子问题答案加一位贡献。
  • 打表:一次遍历得全部结果。

原理流程

  1. dp[0] = 0。
  2. 按递推式填表。
  3. 返回数组。

代码 / 示例

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:典型线性递推,状态为数值,转移靠位运算。