位运算（基础/性质/拆位/试填/恒等式/思维）
一、基础题
⭐ 3370. 仅含置位位的最小整数（20250424）
Details
给你一个正整数 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;
}
}⭐ 231. 2 的幂
Details
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1示例 2：
输入：n = 16
输出：true
解释：24 = 16示例 3：
输入：n = 3
输出：false提示：
-231 <= n <= 231 - 1
**进阶：**你能够不使用循环/递归解决此问题吗？
判断一个数是不是2的次幂，最简单的方法就是，每次使用n除以2，判断n最后是否等于1，如果等于就是2的次幂，否则就不是。
还有另一种思路，我们用归纳法来求解一下。
2 = 10(1)
4=100(1)
8=1000(1)
16=10000(1)
可以看出来是2的次幂的话，二进制表示里面只会有一个1 ，那么 用n异或上n-1的话，结果一定等于0 ， 即
，前提是n必须大于0 ， 因为负数肯定不是2的次幂。
class Solution {
public boolean isPowerOfTwo(int n) {
while(n!= 0 && n % 2 == 0){
n /= 2;
}
return n ==1;
}
}class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}...
3226. 使两个整数相等的位更改次数（20250424）
Details
给你两个正整数 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）
Details
给你一个整数数组 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异或的结果的二进制中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）
Details
给你一个非负整数 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;
}
}二、异或（XOR）的性质
136. 只出现一次的数字（20250411）
Details
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
因为只有一个元素只出现了一次，可以使用异或的特性求解，相同为0直接可以将相同的两个元素删除掉。
137. 只出现一次的数字 II（待更新）
260. 只出现一次的数字 III（待更新）
Details
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
第一次遍历之后，就得到两个不同元素的异或值，第二次遍历求不同位。
三、与或（AND/OR）的性质
AND的数越多，结果越小；OR的数越多，结果越大。
2980. 检查按位或是否存在尾随零（20250729）
Details
给你一个 正整数 数组 nums 。
你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中 至少 存在一个尾随零。
例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。
如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。示例 2：
输入：nums = [2,4,8,16]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110"，存在一个尾随零。
其他按位或运算结果存在尾随零的可能选择方案包括：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 以及 (2, 4, 8, 16) 。示例 3：
输入：nums = [1,3,5,7,9]
输出：false
解释：不存在按位或运算结果存在尾随零的选择方案。提示：
2 <= nums.length <= 1001 <= nums[i] <= 100
参考灵神的题解：判断是否有至少两个偶数（Python/Java/C++/Go）
首先我们要明白，什么是按位或？只要两个数中有一个1，结果就为1，比如下面的例子：
0 | 0 = 0；
0 | 1 = 1；
1 | 0 = 1；
1 | 1 = 1；
然后我们从题目中第一个例子大概能够总结出，这道题是判断偶数的个数问题，因为只有偶数，末尾才有0出现。
所有只要当偶数大于等于2的时候，就返回true，否则返回false。
class Solution {
public boolean hasTrailingZeros(int[] nums) {
// 偶数个数大于2就行
int cnt = 0;
for (int x: nums) {
if (x % 2 == 0) {
cnt++;
if (cnt >= 2) {
return true;
}
}
}
return false;
}
}...
2419. 按位与最大的最长子数组
Details
给你一个长度为 n 的整数数组 nums 。
考虑 nums 中进行 **按位与（bitwise AND）**运算得到的值 最大 的 非空 子数组。
- 换句话说，令
k是nums任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于k的子数组。
返回满足要求的 最长 子数组的长度。
数组的按位与就是对数组中的所有数字进行按位与运算。
子数组 是数组中的一个连续元素序列。
示例 1：
输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3]，所以返回 2 。示例 2：
输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4 。
能得到此结果的最长子数组是 [4]，所以返回 1 。提示：
1 <= nums.length <= 1051 <= nums[i] <= 106
参考灵神的题解：脑筋急转弯，从两次遍历到一次遍历（Python/Java/C++/C/Go/JS/Rust）
AND的性质是，参与AND的元素越多，AND的结果越小。
AND求最大值，肯定是nums中的mx值，所以我们只需要找到数组中最大值mx的最长连续个数就是答案。
这里需要注意的就是，因为求的是最场子数组的长度，最长子数组是连续的元素序列。
class Solution {
public int longestSubarray(int[] nums) {
// 返回最大值的个数？
// 子数组 连续的一个或者多个元素组成的数组
int ans = 0;
int mx = nums[0];
// mx
for (int x: nums) {
if (x > mx) {
mx = x;
}
}
int cnt = 0;
for (int x: nums) {
if (x == mx) {
cnt++;
ans = Math.max(ans, cnt);
} else {
cnt = 0;
}
}
return ans;
}
}Changelog
4c155-on