五、位运算
有必要学习掌握一下位运算的知识点！！灵神位运算题单:
一、基础知识点
1.1、位运算
1.1.1、按位与（AND， x & y）
按位与，只有两个都位1的时候，结果才为1，（x & y）
| x | y | x & y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
1.1.2、按位或（OR， x | y）
只要有一个1，结果就为1，（x | y）
| x | y | x | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
1.1.3、取反（NOT，~x）
取反，0变为1，1变为0
| x | ~x |
|---|---|
| 0 | 1 |
| 1 | 0 |
1.1.4、异或（XOR，x ^ y）
异或操作是一个数学运算符，用于逻辑运算，符号为^，多数情况下使用xor表示异或。
简而言之，相同为 0， 不同为 1；【0 xor 0 = 0， 1 xor 1 = 0，0 xor 1 = 1】
| x | y | x ^ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
异或运算法则：
- a ^ b = b ^ a
- a ^ b ^ c = a ^ (b ^ c)
- 例如：x=0101, y=1011， x^y=1110
异或的应用：
- 交换两个变量的值，除了通常使用的借用中间变量进行交换外， 还可以利用异或操作，仅适用两个变量进行交换，如：a=a^b, b=a^b, a=a^b, 完成对 a 和 b 的交换。
1.2 位运算操作
| 操作 | 含义 | 实例 |
|---|---|---|
| x & (x-1) | 清除x最低位的1，如果结果是0，那么x是0或者是2 ^ k | 1101 & 1100 -> 1100 |
| x | (x + 1) | 将x最低位的0变成为1 | 1101 | 1110 -> 1111 |
| x & -x | 提取最低位的1 | x = 1100 , -> 4 |
| ~x & (x + 1) | 提取最低位的0 | x = 1101, -> 2 |
1.3、集合与位运算
1.3.1、集合与集合
交集、并集、补集
其中 & 表示按位与，| 表示按位或， ⊕ 表示按位异或，∼ 表示按位取反。
- 按位与
- 按位或
- 对称差，
{0,2,3} ⊕ {0,1,2} -> {1,3}
1.3.2、集合与元素
补码：在补码系统中，负数-s的表示是正数s的按位取反后加一。
s = 101100
~s = 010011
~s + 1 = 010100 // -s表示s的补码，按位取反后加一
s&(-s) = 000100s = 101100
s-1 = 101011
s&(s-1) = 101000集合可以用二进制表示，二进制从低到高，第i位为1表示i在集合中，为0表示i不在集合中。例如集合{0,2,3}可以用二进制1101表示；反过来，二进制1101就对应集合{0,2,3}。
- 计算二进制中1的个数，也就是集合大小
- 计算二进制的长度，减一后得到集合最大元素
- 计算二进制尾零个数，也就是集合最小元素。
调用下方函数的时间复杂度都是O(1)
// 判断最低是1的位置, 1101 -> 0, 1100 -> 2
System.out.println(Integer.numberOfTrailingZeros(12)); // 2
// 判断二进制前面有多少个0， 1101 -> 28, 1100 -> 28
System.out.println(Integer.numberOfLeadingZeros(12));| 术语 | Python | Java |
|---|---|---|
| 集合大小 | s.bit_count() | Integer.bitCount(s) |
| 二进制长度 | s.bit_length() | 32-Integer.numberOfLeadingZeros(s) |
| 集合最大元素 | s.bit_length()-1 | 31-Integer.numberOfLeadingZeros(s) |
| 集合最小元素 | (s&-s).bit_length()-1 | Integer.numberOfTrailingZeros(s) |
1.3.3 、遍历集合
设元素范围从0到n-1，枚举范围中的元素i, 判断i是否在集合s中。
// set {0, 2, 3}
int s = 13;
for (int i = 0; i < 10; i++) {
// s可以表示为集合的二进制形式，所以右移 i 位，就到了第 i 位,
// & 1判断最后一位是否为1，如果为1则表示在集合中
if (((s >> i) & 1) == 1) {
System.out.println(i); // 0, 2, 3
}
}# set {0, 2, 3}
s = 13
for i in range(n):
if (s >> i) & 1: # i 在 s 中
# 处理 i 的逻辑
print(i) # 0, 2, 3也可以直接遍历集合s中的元素，不断计算集合最小元素、去掉最小元素，直到集合为空。
for(int t = s; t>0;t &= t-1){
int i = Integer.numberOfTrailingZeros(t); // 返回 1 的最低位
// 处理i的逻辑
}t = s
while t:
lowbit = t & -t
t ^= lowbit
i = lowbit.bit_length() - 1
# 处理i的逻辑1.3.4、枚举集合
1.3.4.1、枚举所有集合
设元素范围从 0 到 n−1，从空集 ∅ 枚举到全集 U：
// 这里n是多少？
// 就是遍历[0, n-1)
for(int s = 0; s < (1 << n);s++){
// 处理s的逻辑
}# coding...1.3.4.2、枚举非空子集
设集合为s，从大到小枚举s的所有非空子集sub：
为什么sub = (sub-1) & s?
- 暴力做法是从 s 出发，不断减一，直到 0。但这样做，中途会遇到很多并不是 s 的子集的情况。例如 s=10101 时，减一得到 10100，这是 s 的子集。但再减一就得到 10011 了，这并不是 s 的子集，下一个子集应该是 10001。
如何快速跳到下一个子集呢？比如，怎么从 10100 跳到 10001？
- 普通的二进制减法，是 10100−1=10011，也就是把最低位的 1 变成 0，同时把最低位的 1 右边的 0 都变成 1。 压缩版的二进制减法也是类似的，对于 10100→10001，也会把最低位的 1 变成 0，对于最低位的 1 右边的 0，并不是都变成 1，只有在 s=10101 中的 1 才会变成 1。怎么做到？减一后 & 10101 就行，也就是 (10100−1) & 10101=10001。
int s = 13; // 1101
// 为什么要(sub-1) & s ? 将sub转化成下一个数
for (int sub = s; sub > 0; sub = (sub - 1) & s) {
// 1101
// 13, 12, 9, 8, 5, 4, 1
// 1101, 1100, 1001, 1000, 0101, 0100, 0001
System.out.println(sub);
}sub = s
while sub:
# 处理 sub 的逻辑
sub = (sub-1) & s1.3.4.3、枚举子集（包含空集）
如果要从大到小枚举s的所有子集sub（从s枚举到空集），可以这样写：
其中 Java 和 C++ 的原理是，当 sub=0 时（空集），再减一就得到 −1，对应的二进制为 111⋯1，再 &s 就得到了 s。所以当循环到 sub=s 时，说明最后一次循环的 sub=0（空集），s 的所有子集都枚举到了，退出循环。
int s = 13; // 1101
int sub = s;
do {
// 处理sub的逻辑
// 13, 12, 9, 8, 5, 4, 1, 0
System.out.println(sub);
sub = (sub - 1) & s;
} while (sub != s);sub = s
while True:
# 处理 sub 逻辑
if sub == 0:
break
sub = (sub - 1) & s # 保证只有s中有的1为1二、题单
2.1、基础题
3370. 仅含置位位的最小整数（20250424更新）
给你一个正整数
n。返回 大于等于
n且二进制表示仅包含 置位 位的 最小 整数x。置位 位指的是二进制表示中值为
1的位。
先求n对应的二进制的位数x，然后在求最多x位的二进制能表示的最大值。
class Solution {
public int smallestNumber(int n) {
// 假如n的二进制位数为x，求最多x位的二进制的最大值
int x = 32 - Integer.numberOfLeadingZeros(n);
// 这个位运算就相当于求2的x次方，真厉害。
return (1 << x) - 1;
// return (int)Math.pow(2, x) -1;
}
}3226. 使两个整数相等的位更改次数（20250424更新）
给你两个正整数
n和k。你可以选择
n的 二进制表示 中任意一个值为 1 的位，并将其改为 0。返回使得
n等于k所需要的更改次数。如果无法实现，返回 -1。
从集合的角度理解，每次操作相当于去掉集合n中的一个元素。
要能把n变成k，k必须是n的子集。如果不是，返回-1.
如果k是n的子集，答案为从n中去掉k后集合大小，即 n⊕k 的二进制中的 1 的个数。
class Solution {
public int minChanges(int n, int k) {
// Integer.bitCount(x)表示x二进制中1的个数
// n & k 表示两个集合的交集
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
}
}1356. 根据数字二进制下 1 的数目排序（20250426更新）
给你一个整数数组
arr。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
通过优先级队列的自定义排序，遍历数组存入优先级队列中，然后出队将数据存入返回的容器。
class Solution {
public int[] sortByBits(int[] arr) {
// 优先级队列, 自定义排序
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
} else {
return a[0] - b[0];
}
});
for (int x : arr) {
int cnt = Integer.bitCount(x);
queue.add(new int[] { cnt, x });
}
// 什么时候length, 什么是否length(), 什么时候size()
// 字符串 调用length()方法
// 数组 调用length属性
// 列表 调用size()方法
int[] ans = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
ans[i] = queue.poll()[1];
}
return ans;
}
}class Solution {
public int[] sortByBits(int[] arr) {
// 将int[] 转化成Integer[] 以使用Comparator
Integer[] boxedArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(boxedArr, (a, b) -> {
int bita = Integer.bitCount(a);
int bitb = Integer.bitCount(b);
return bita == bitb ? a - b : bita - bitb;
});
// 转回int[]
return Arrays.stream(boxedArr).mapToInt(i -> i).toArray();
}
}补充：
- stream流中boxed()的使用
- 将原始类型转化成盒式类型
- 将原始类型转化成盒式类型：
Integer[] boxedArr = Arrays.stream(arr).boxed().toArray(Integer[]::new); - 将盒式类型转成原始类型 ：
int[] arr = Arrays.stream(boxedArr).mapToInt(i -> i).toArray();
461. 汉明距离（20250428更新）
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数
x和y，计算并返回它们之间的汉明距离。
直接求x和y异或的结果的二进制中1的个数。
Integer.bitCount(x)表示x的二进制表示中1的个数，不是表示二进制有多少位。
class Solution {
public int hammingDistance(int x, int y) {
// 求 x 异或 y之后1的个数，
int s = x ^ y;
// Integer.bitCount(x) 表示一个数的二进制位有多少个1，如5的二进制位101，返回2
return Integer.bitCount(s);
}
}Integer.numberOfLeadingZeros(x); // 计算前导0的个数
Integer.numberOfTrailingZeros(x); // 计算最低位1的下标（下标从0开始）1342. 将数字变成 0 的操作次数（20250428更新）
给你一个非负整数
num，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
题目的考点就是判断num是偶数还是奇数，如果是偶数num变成num/2， 如果num是奇数，num变成num-1；
判断num是否为偶数：(num & 1) == 0
判断num是否为奇数：(num & 1) == 1
因为按位与只有两个都为1的时候，结果才为1，如果最后1位是1的话，就表示num是奇数。
476. 数字的补数（20250428更新）
手写2进制转10进制代码。
API实现2进制转10进制。
class Solution {
public int findComplement(int num) {
// 1. 32 - Integer.numberOfLeadingZeros(num) 计算num二进制的有效位数
// 2. (1 << (32 - Integer.numberOfLeadingZeros(num))) - 1 生成一个全为1的掩码，也就是有效能表示的最大数
// 3. 异或操作，将原数与掩码异或，翻转所有有效位。
return num ^ (1 << (32 - Integer.numberOfLeadingZeros(num))) - 1;
}
}2.2、异或（XOR）的性质
136. 只出现一次的数字（20250411更新）
给你一个 非空 整数数组
nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
因为只有一个元素只出现了一次，可以使用异或的特性求解，相同为0直接可以将相同的两个元素删除掉。
137. 只出现一次的数字 II（待更新）
260. 只出现一次的数字 III（待更新）
给你一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
第一次遍历之后，就得到两个不同元素的异或值，第二次遍历求不同位。
Changelog
d3a6d-on