一篇讲透位运算：从基础操作到经典技巧（Java 版，附速查表 + LeetCode 题单）

• 🏠博客主页：小谢同学的小破站
• ✍️本文由 小谢同学的小破站 原创，首发于 CSDN 💻
• ☕JavaSE专栏：JavaSE
• 📗JavaEE初阶专栏：JavaEE初阶
• 📘JavaEE进阶专栏：JavaEE进阶
• 🧩数据结构专栏：数据结构
• ⚙️算法专栏：算法
• 📚MySQL初阶专栏：MySQL初阶
• 🔐MySQL进阶专栏：MySQL进阶
• 🌐计算机网络专栏：计算机网络
• 💻C语言专栏：C语言
• 👍欢迎点赞👍 收藏⭐ 留言📝，发现错误欢迎指正！
• ✨脚踏实地，持续深耕，奔赴自己的目标✨
  ----- 📌分割线 📌-------

位运算算法

• 一、基础位运算
• 二、获取一个数 n 二进制表示中的第 x 位
• 三、将第 x 位修改成 1
• 四、将第 x 位修改成 0
• 五、提取一个数中最右侧的 1（lowbit）
• 六、干掉一个数中最右侧的 1
• 七、位运算的优先级
• 八、异或运算的运算律
• 九、速查表与刷题清单
  • 🧾 Java 位运算速查表
  • 📚 配套刷题清单（LeetCode）
  • 🎯 三条心法
    
    

前言：
   这里是小谢同学整理有关算法相关的位运算笔记。笔记用于自我复盘巩固，有错误欢迎大家指出，专栏还有 Java、网络、C 语言等系列笔记欢迎翻阅.同时也希望我这篇文章能够帮助到你~

1. 基础位运算

首先我们先来回顾一下我们Java阶段的基础位运算的符号~

运算符	名称	说明与口诀
<<	左移	二进制整体左移，低位补 0，相当于乘 2
>>	算术右移	高位补符号位（负数补 1），相当于除以 2 向下取整
>>>	无符号右移	高位一律补 0，Java 独有
~	按位取反	0 变 1，1 变 0
&	按位与	有 0 就是 0
|	按位或	有 1 就是 1
^	按位异或	相同为 0，相异为 1（等价于无进位相加）

三个最容易混淆的，我们只需要记住口诀即可：

• &：有 0 就是 0 —— 想「清零 / 筛选」时用它；
• |：有 1 就是 1 —— 想「置 1 / 合并」时用它；
• ^：相同为 0，相异为 1 —— 可以理解为「不进位的加法」。

举个异或的例子，5 ^ 3：

  101   (5)
^ 011   (3)
------
  110   (6)    逐位比较：相同得 0，不同得 1

只有当两个而进制位不相同的时候,对应的二进制位上面的值位1,相同的时候为0;

其次当两个相同的数字进行异或的时候,得到的结果为0
当一个数字和0异或的时候得到的结果为数字本身

那为什么说异或等价于「无进位相加」？我们来看 1 + 1 = 10，如果不允许进位，本位就只剩下 0，这正好就是异或的结果。这个视角在后面推导异或运算律时非常好用。

2. 获取一个数 n 二进制表示中的第 x 位

目标：判断第 x 位（从最低位开始，编号从 0 起）是 0 还是 1。

做法：先把整个数右移 x 位，让目标位落到最低位；再和 1 按位与，把其余位全部清掉。
代码实现:

(n >> x) & 1

举一个比较简单的例子:
 425的第多少多少位是0还是1

注意 >> 还是 >>>？
 处理非负整数的位时，n >> x 和 n >>> x 结果一样，随便用。
 但如果 n 可能是负的（比如做状态压缩时不小心溢出了），>> 会补符号位 1，导致高位的 1 被"搬"下来，结果就错了——这种场景请用 n >>> x。
 日常刷题刷下标、取位，用 >> 即可。

3. 将第 x 位修改成 1

思路：构造一个[只有第 x 位是 1、其余全为 0]的二进制，然后按位或上去。因为 | 是「有 1 就是 1」，目标位会被顶成 1，其余位保持原样。

n | (1 << x)

还是以425为例子,此时我们想要修改425的第二位上的0为1

4. 将第 x 位修改成 0

思路：这次需要「只有第 x 位是 0、其余全为 1」的掩码。先把 1 << x 整体取反 ~，就得到了这个掩码，再按位与。

n & ~(1 << x)

形式上和修改成1类似,只不过我们这里需要加一个取反操作

还是以:425为例子,我们需要修改425

5. 提取一个数中最右侧的 1（lowbit）

这是一个极度经典的技巧，写法只有一个：

n & -n

它的结果是一个新的数：只保留 n 的二进制里最右侧的那个 1，其余位全部为 0。

手算演示（用补码理解负数：-n = ~n + 1）：

 n   = 0101100
-n   = 1010100     ← 补码 = 取反 + 1
----------------
n&-n = 0000100     ← 成功提取出最右侧的 1

6. 干掉一个数中最右侧的 1

与 lowbit 成对出现的另一个经典写法：

n & (n - 1)

此时为什么成立：n - 1 会把 n 里最右侧的那个 1 变成 0，同时它右边的所有 0 全部变成 1；再和原数 n 按位与，右侧这一段就被整体清掉了。

此时我可以给大家进行演示一遍:

 n      = 0110
 n - 1  = 0101
----------------
n&(n-1) = 0100     ← 此时最右侧的 1 就被干掉了

经典应用 1：统计二进制中 1 的个数（汉明重量）

每次干掉最右侧的一个 1，直到数字变成 0，循环次数就是 1 的个数。这就是 Integer.bitCount 的经典实现 Integer.bitCount()：

public static int countOnes(int n) {
    int cnt = 0;
    while (n != 0) {
        n &= n - 1;          // 每次干掉最右侧的 1
        cnt++;
    }
    return cnt;

经典应用 2：判断一个数是不是 2 的幂

2 的幂的二进制里只有一个 1，干掉这个 1 之后必然变成 0：

public static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

注意 n > 0 不能省：0 是 (0 & -1) == 0，会被误判；负数也满足这个式子——Integer.MIN_VALUE（即 1 << 31）是负数，但它的二进制里同样只有一个 1，Integer.MIN_VALUE & (Integer.MIN_VALUE - 1) == 0 也成立。所以判断 2 的幂必须带上 n > 0。

7. 位运算的优先级

一句话结论：位运算优先级低、且各不相同，能加括号就加括号。
Java 中相关优先级从高到低大致是：

算术运算 (+ - * / %)  >  移位 (<< >> >>>)  >  关系 (><>=<=)  >  相等 (== !=)  >  &  >  ^  >  |  >  &&  >  ||

也就是说：移位比加减低，&/^/| 比 == 还低，很容易写出反直觉的表达式：

// 到底是 (n >> x) & 1 还是 n >> (x & 1)？不查表根本就猜不出来
int bit = (n >> x) & 1;                          

// Java 中的经典组合写法，全部加括号才安全
int res = (n & ~(1 << x)) | (1 << y);

我们与其背这张表，不如养成习惯：只要位运算和其他运算符混用，就显式加括号

8. 异或运算的运算律

异或 ^ 满足三条常用运算律：

1. 交换律：a ^ b == b ^ a
2. 结合律：(a ^ b) ^ c == a ^ (b ^ c)
3. 自反性：a ^ a == 0，并且 a ^ 0 == a

用「无进位相加」的视角很好理解自反性：两个一模一样的数相加，每一位都是 1 + 1，不进位的情况下本位结果全是 0，所以整体异或为 0。

经典应用：只出现一次的数字

LeetCode 136. Single Number
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

我们只需要将所有的元素全部都异或在一起即可:

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
}

进阶：LeetCode 260「只出现一次的数字 III」中，两个只出现一次的数异或后结果非 0，此时用 lowbit 把数组按某一位分成两组，就退化成了本题：

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int x : nums) xor ^= x;

        int lowbit = xor & -xor;      // 取出 xor 中最右侧的 1，用于分组
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x & lowbit) == 0) a ^= x;
            else                   b ^= x;
        }
        return new int[]{a, b};
    }
}

9. 速查表与刷题清单

🧾 Java 位运算速查表

需求	写法（Java）
取第 x 位	(n >> x) & 1
第 x 位置 1	n |= (1 << x)
第 x 位清 0	n &= ~(1 << x)
第 x 位取反	n ^= (1 << x)
提取最右侧的 1（lowbit）	n & -n
干掉最右侧的 1	n & (n - 1)
判断 2 的幂	n > 0 && (n & (n - 1)) == 0
判断奇偶	(n & 1) == 1
统计 1 的个数	Integer.bitCount(n)
最低位的 0 变 1	n | (n + 1)
交换两数（不借临时变量）	a ^= b; b ^= a; a ^= b;
二进制字符串	Integer.toBinaryString(n)
需要 > 32 位的掩码	1L << x（务必加 L）

📚 配套刷题清单（LeetCode）

题目	难度	考察点
136. 只出现一次的数字	简单	异或自反性
191. 位 1 的个数	简单	n & (n-1)
231. 2 的幂	简单	n & (n-1)
342. 4 的幂	简单	掩码 + 位判断
338. 比特位计数	简单	动态规划 + 位运算
190. 颠倒二进制位	简单	>>> 无符号右移
137. 只出现一次的数字 II	中等	逐位计数
260. 只出现一次的数字 III	中等	lowbit 分组
78. 子集	中等	二进制枚举
201. 数字范围按位与	中等	公共前缀

🎯 三条心法

1. 口诀优先：& 有 0 就是 0，| 有 1 就是 1，^ 相同为 0 相异为 1（无进位相加）；
2. 能加括号就加括号：Java 里 n & 1 == 1 连编译都过不去，别为难自己；
3. 移位位数 ≤ 31 用 int，超过就用 1L：1 << 32 在 Java 里等于 1，这是个静默的坑。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_93799892/article/details/166789338