位运算有哪些必须掌握的基础操作和技巧？

简化版

位运算直接操作整数的二进制位，常用运算符：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（算术右移）、>>>（无符号右移，Java）。核心技巧：判断第 i 位 (n >> i) & 1；把第 i 位置 1 n | (1 << i)；清零 n & ~(1 << i)；翻转 n ^ (1 << i)；去掉最低位的 1 n & (n - 1)（判 2 的幂、数 1 的个数常用）；取最低位的 1 n & (-n)。异或的性质（x^x=0、x^0=x）是「找单独出现数字」类题的核心。

详细版

六个运算符：

运算符	含义	例（4 位）
`&` 与	都为 1 才 1	`1100 & 1010 = 1000`
`\|` 或	有 1 就 1	`1100 \| 1010 = 1110`
`^` 异或	不同为 1	`1100 ^ 1010 = 0110`
`~` 取反	0↔1	`~1100 = ...0011`（含符号位）
`<<` 左移	×2ᵏ	`0011 << 1 = 0110`
`>>` / `>>>`	算术/逻辑右移	`>>` 补符号位，`>>>` 补 0

常用位技巧（务必背熟）：

(n >> i) & 1          // 取第 i 位（0 或 1）
n | (1 << i)          // 第 i 位置 1
n & ~(1 << i)         // 第 i 位清 0
n ^ (1 << i)          // 第 i 位翻转
n & (n - 1)           // 去掉最低位的 1（消掉最右边的 1）
n & (-n)              // 取出最低位的 1（lowbit）
n & (n - 1) == 0      // 判断是否为 2 的幂（n>0）

异或三大性质： x ^ x = 0、x ^ 0 = x、满足交换律结合律 → 一组数全异或，成对的抵消，剩下单独的。

完整版教学

一、为什么要用位运算

计算机底层用二进制存整数，位运算直接在二进制位上操作，极快（单条 CPU 指令），且能省空间（用一个 int 的 32 位表示 32 个布尔状态 = 状态压缩）。面试考位运算，考的是你对二进制的理解和这些固定技巧的熟练度——它们不是推导出来的，是要背下来当工具用的。

二、六个运算符的关键细节

&（与）：常用来「取某些位」——和掩码 & 保留掩码为 1 的位。n & 1 判奇偶（结果 1 是奇数）。
|（或）：常用来「置某些位为 1」。
^（异或）：最重要，「相同为 0、不同为 1」。它是「无进位加法」，性质极多（下节详述）。
~（取反）：所有位翻转，注意包括符号位，~n = -n - 1。
<<（左移）：n << k = n × 2ᵏ（不溢出时）。
>>（算术右移）：右移补符号位（负数补 1），n >> k ≈ n / 2ᵏ 向下取整。
>>>（逻辑右移，Java 特有）：右移补 0，用于把负数当无符号数处理（如颠倒二进制位、数 1 的个数时必须用 >>> 避免符号位无限补 1 死循环）。

三、单个位的四种操作

给定整数 n，操作它的第 i 位（从 0 开始，最低位是第 0 位）：

取第 i 位：(n >> i) & 1——把第 i 位移到最低位，再 & 1 取出来。
置 1：n | (1 << i)——1 << i 造一个只有第 i 位是 1 的掩码，| 上去。
清 0：n & ~(1 << i)——掩码取反（第 i 位是 0、其余 1），& 保留其余、抹掉第 i 位。
翻转：n ^ (1 << i)——异或第 i 位掩码，该位 0↔1。

这四个是「状态压缩 DP」「位图」的基本功。

四、两个王牌技巧：n&(n-1) 和 n&(-n)

① n & (n - 1)：消掉最低位的 1

n - 1 会把 n 最低位的 1 变成 0、其右边的 0 全变 1；再和 n 相与，最低位的那个 1 及右边全部清零，其余不变——效果是「抹掉最右边的一个 1」。

应用：数二进制中 1 的个数——反复 n = n & (n-1)，执行几次就有几个 1（比逐位检查快，只循环「1 的个数」次）。
应用：判断 2 的幂——2 的幂二进制只有一个 1，n > 0 && (n & (n-1)) == 0 即是。

② n & (-n)：取出最低位的 1（lowbit）

负数 -n = ~n + 1（补码），和 n 相与恰好只保留最低位的 1，其余为 0。这是**树状数组（Fenwick Tree）**的核心操作。

五、异或的威力：找「单独出现」的数

异或性质：x^x=0、x^0=x、交换结合律。推论——一组数字全部异或起来，出现偶数次的两两抵消（变 0），最后剩下出现奇数次的那个。

只出现一次的数字（136）：其余都出现两次 → 全体异或，成对抵消，答案就是那个单独的数。O(n) 时间 O(1) 空间，惊艳。
交换两数不用临时变量：a^=b; b^=a; a^=b;。
找缺失数字（268）：把 [0,n] 和数组元素全异或，剩下的就是缺失值。

六、用固定宽度验证掩码语义

位运算必须先约定“位宽”和“第 0 位在最低位”。下面用 8 位展示 n=44=00101100₂；真实 Java int 是 32 位，~ 和负数运算会连符号位一起参与。掩码不是魔法，它只是用每个位置上的 0/1 决定保留、设置或翻转。

n              = 00101100
1 << 3         = 00001000
n | (1 << 3)   = 00101100  // 第 3 位原本就是 1
n & ~(1 << 3)  = 00100100  // 清掉第 3 位
n ^ (1 << 1)   = 00101110  // 翻转第 1 位
n & (n - 1)    = 00101000  // 清掉最低位的 1

校验维度	本题必须保持的结论
循环/递推不变量	掩码为 1 的位置才可能影响目标位；`n&(n-1)` 每轮严格减少一个 1。
边界条件	`1 << i` 的 `i` 会按 Java 规则取低 5 位，且 `~` 的结果是完整 32 位补码。
复杂度与代价	单次位操作 O(1)；用位图压缩状态可把 32 个布尔值放入一个 int。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：掩码为 1 的位置才可能影响目标位；n&(n-1) 每轮严格减少一个 1。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“n = 00101100”开始手推，最后应得到“n & (n - 1) = 00101000 // 清掉最低位的 1”。
边界复核：1 << i 的 i 会按 Java 规则取低 5 位，且 ~ 的结果是完整 32 位补码。
代价复核：单次位操作 O(1)；用位图压缩状态可把 32 个布尔值放入一个 int。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“掩码为 1 的位置才可能影响目标位；n&(n-1) 每轮严格减少一个 1。”这条正确性主线不能省。

八、常见误区与追问

误区：左移始终等价于乘以 2 的幂。 只有不发生定宽整数溢出时才等价，移入符号位后数值语义会改变。
误区：~1100 的结果就是 0011。 必须先确定固定宽度；Java int 中 ~12 会翻转全部 32 位，结果是 -13。
误区：n & (n - 1) == 0 可以直接判断 2 的幂。 还必须要求 n > 0，否则 0 也会误通过。
追问：为什么 n & -n 能取出 lowbit？ -n=~n+1，最低位 1 右侧在两者中都为 0，该位同时为 1，更高位则互相抵消。
追问：Java 中 >> 和 >>> 的差异是什么？ >> 用符号位填充高位，>>> 一律补 0；处理无符号位模式时通常用后者。
追问：位掩码适合表示多少种状态？ 一个 k 位掩码能表示 2^k 个子集，但枚举全部掩码仍需指数时间。

九、加强记忆

位运算 = 直接操作二进制位的固定工具集，要背熟：运算符 & | ^ ~ << >> >>>（>>> 补 0、>> 补符号位）；单个位 取 (n>>i)&1、置 1 n|(1<<i)、清 0 n&~(1<<i)、翻转 n^(1<<i)；两个王牌 n&(n-1) 消掉最低位 1（数 1 的个数、判 2 的幂）和 n&(-n) 取最低位 1（树状数组 lowbit）；异或性质 x^x=0、x^0=x 用来「一组数异或抵消偶数次、剩下奇数次」（只出现一次的数字）。这些是所有位运算题的地基。

简化版

详细版