Java 中位运算符有与（&）、或（|）、非（～）、异或（^）、左移（<<）、右移（>>）、无符号右移（>>>），只针对 int 类型有效，也可以作用于 byte、short、char、long，当为这四种类型时，JVM 会先把它们转换为 int 再操作。使用位运算符可以优化一些场景的运行速度，有时也可以简化代码，掌握一些位操作的技巧还是很有必要的，下面是我总结的 LeetCode 上一些位操作算法问题。
1. 在 O（n）时间内求 0 ～ N 的所有整数的二进制表示中 1 的个数
题目描述：给定一个非负整数 num，求 0 到 num 所有数的二进制表示中 1 的个数，最好在一次遍历 O（n）时间内完成，而且不能使用内置 API。
分析：求二进制表示中 1 的个数可以使用 Integer.bitcount() 实现，但是题目要求不能使用其他内置函数，所以好像没什么办法可以 O(1) 时间内求一个数的 bitcount。这种情况下，可以看下实际的例子。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 0 | 1 | 10 | 11 | 100 | 101 | 110 |
| 0 | 1 | 1 | 2 | 1 | 2 | 2 |
上面表格中第二行为 int 的二进制表示，第三行为 bit 为 1 的个数，仔细观察可以发现每个 num 的 bitcount 为 1 加上 除去最高位后的 bitcount，例如 2 的 bitcount 为 1 加上 0 的bitcount，3 的 bitcount 为 1 加上 1 的 bitcount，6 的 bitcount 为 1 加上 2 的 bitcount。所以可以通过 0 和 1 的 bitcount，计算出之后每个数的 bitcount。
代码如下：
// 在 O（n）时间内求 0 ～ N 之间整数的 bitcount
public int[] countBits(int num) {
if (0 == num) {
return new int[]{0};
}
if (1 == num) {
return new int[]{0, 1};
}
int[] bitCounts = new int[num + 1];
bitCounts[0] = 0;
bitCounts[1] = 1;
int offset = 1;
for (int i = 2; i <= num; i ++) {
if (offset * 2 == i) {
offset = i;
}
bitCounts[i] = bitCounts[i - offset] + 1;
}
return bitCounts;
}
除了上面的解法外，计算 bitcount 还有其他方式，b[n] = b [n >> 1] + n & 1，b[n >> 1] 为 n 除去最后一位的 bitcount，再加上 n & 1 为最后一位是否为 1。
2. 给定包含不同整数的集合，返回它的所有可能子集
题目描述：返回一个整数集合的所有子集，子集不能重复
分析：对于任何一个子集，第 i 个整数是否包含，可以使用一个整数的第 i 位是否为 1 表示，所以从 0 ～ 2^n - 1 个整数刚好可以对应集合的 2^n 个子集。
// 求集合的所有子集
public List<List<Integer>> subsets(int[] nums) {
int setSize = (int)Math.pow(2, nums.length);
List<List<Integer>> sets = new ArrayList<>(setSize);
for (int i = 0; i < setSize; i ++) {
List<Integer> set = new ArrayList<>();
for (int j = 0; j < nums.length; j ++) {
if (((i >> j) & 1) == 1) {
set.add(nums[j]);
}
}
sets.add(set);
}
return sets;
}
3. 求 m ～ n 内所有整数进行 & 运算后的结果
LeetCode 201. Bitwise AND of Numbers Range
题目描述：给定 m 和 n，其中 0 <= m <= n <= 2^31 - 1，求 m ～ n 内所有整数进行 & 运算后的结果
分析：这里求的是所有整数进行 & 运算后的结果，如果有两个整数 & 运算后为 0，那么最后结果肯定为 0。当 m 和 n 的最高位不同时，那么一定存在这么一个数 10..0，它与 n 计算的结果为 0。而 m 和 n 的最高位相同时，那么最后结果肯定包含最高位，接下来求除去最高位后的整数运算的结果，重复之前的过程即可。
// 求 m ～ n 内所有整数进行 & 运算后的结果
public int rangeBitwiseAnd(int m, int n) {
if (m == n) {
return m;
}
int result = 0;
while (m < n) {
int mHightBit = Integer.highestOneBit(m);
int nHightBit = Integer.highestOneBit(n);
if (mHightBit != nHightBit) {
break;
}
result |= mHightBit;
m &= (mHightBit - 1);
n &= (nHightBit - 1);
}
return result;
}
4. 求二进制表示中 1 的个数
题目描述：给定一个无符号整数，求它的二进制表示中 1 的个数。
分析：
1.一个无符号整数二进制有 32 位，一种通用的方式是计算 32 位 bit 是否为 1，使用 n & 1 计算最后一位是否为 1，时间复杂度为 O(32)。
// 求二进制表示中 1 的个数
public int hammingWeight(int n) {
int num = 0;
while (n != 0) {
num += n & 1;
n = n >>> 1;
}
return num;
}
2.除了利用 n & 1 计算最后一位为 1，还有另外一种方法，n &= n - 1 可以消除最后一位为 1 的位，例如 n = 1100，那么 n - 1 = 1011，与运算之后的结果为 1000，消除了倒数第 3 位的 1 bit，为负数时也是一样，这种方式的时间复杂度与 1 的位数有关。
// 求二进制表示中 1 的个数
public int hammingWeight(int n) {
int num = 0;
while (n != 0) {
n &= n - 1;
num ++;
}
return num;
}
3.其实 Integer 类有个静态方法 bitCount() 计算 1 的个数，采用二分法的思想，先计算每两位中 1 的个数，再计算每四位、每八位、每十六位，最后把两个十六位的个数相加。其中第一步求每两位中 1 的个数的方法很巧妙，i - (i >>> 1)即位 1 的个数，例如 11 - 01 = 10，11 中 1 的个数刚好为 2（10），对于 32 位的整数来说，移位后还需要把偶数位改为 0，所以还要和 0x55555555 进行与运算。
// 求二进制表示中 1 的个数
public int hammingWeight(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
5. 反转无符号整数的 bit
题目描述：给定一个无符号 32 位整数，反转它的二进制表示中的 bit。
分析：最简单的方式是每次取出最后一位，按相反顺序排列，时间复杂度为 O(32)。有没有什么优化的方式的，可以学习 bitCount 的二分法，依次反转相邻的每十六位、每八位、每四位、每两位到最后相邻的每一位。
// 反转无符号整数的 bit
public int reverseBits(int n) {
// binary swap
n = (n >>> 16) | (n << 16);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
return n;
}
6. 在 O(1) 的时间内检测一个整数是否为 2 的幂
题目描述：判断一个整数是否为 2 的幂。
分析：首先分析 2 的幂一般是 1，10，100，1000，10000 这种类型，在 32 位二进制中只有一位为 1，其他都是 0，这种情况可以使用之前 n &= n - 1 消除最后一位 1 bit 的方式，n & (n - 1) 为 0 则表示只有一位 bit 为 1，当第 32 位为 1 时，此时为负数，不是 2 的幂，可以通过 n > 0 来排除。
// 检测一个整数是否为 2 的幂
public boolean isPowerOfTwo(int n) {
return (n > 0) && (n & (n - 1) == 0)
}
7. 在 O(1) 的时间内检测一个整数是否为 4 的幂
题目描述：判断一个整数是否为 4 的幂。
分析：和上一题相似，4 的幂一般是 1，100，10000，1000000，一个数为 4 的幂，它同时也是 2 的幂，但是 1 bit 所在的位都是奇数位，这个只需要和 0x55555555 与运算不为 0 即可。
public boolean isPowerOfFour(int n) {
return (n > 0) && (n & (n - 1) == 0) && (n & 0x55555555 != 0)
}
8. 找出数组中只出现一次的数
题目描述：给定一个整数数组，所有元素都出现两次除了一个元素，找出只出现一次的元素。要求时间复杂度为线性的，不用额外的空间。
分析：可以利用 n ^ n = 0 的特点，把数组所有元素进行异或运算，最后的结果就是只出现一次的那个元素。
// 其他元素都出现两次
public int singleNumber(int[] nums) {
int result = 0;
for (int n : nums) {
result ^= n;
}
return result;
}
9. 找出数组中只出现一次的数扩展：其他数都出现三次
LeetCode 137. Single Number II
题目描述： 如果所有元素都出现三次只有一个元素只出现一次，在线性时间复杂度内找到这个单独的元素。
分析：
1.元素出现三次的话就不用利用 n ^ n = 0 的特点了，整数在内存中是 32 位二进制，每位只能是 0 和 1，所以可以统计每位 1 出现的个数，再对 3 取余就是单独元素在该位上的结果。这种方式比较通用，如果其他元素都出现四、五、六次都可以利用这种思想，时间复杂度为 O(32N)。
// 其他元素都出现三次
public int singleNumber(int[] nums) {
int result = 0;
int count = 0;
for (int i = 0; i < 32; i ++) {
count = 0;
for (int n : nums) {
count += (n >> i) & 1;
}
result |= (count % 3) << i;
}
return result;
}
2.还有一种解法是用 3 个整数来表示各个 1 bit 的出现次数，one 表示只出现一次的，two 表示出现了两次，出现三次时把该位清零，时间复杂度为 O(N)。
// 其他元素都出现三次
public int singleNumber(int[] nums) {
int one = 0, two = 0, three = 0;
for (int n : nums) {
// 上个状态的 one & n 得到出现两次的结果，再 | 之前的结果，得到出现两次以上的 bits
two |= one & n;
// one ^ n 就是出现一次以上的 bits
one ^= n;
// 再计算出现三次的 bits
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
3.第一种解法是将 32 位分开考虑的，有没有什么方式同时进行 32 位 bit 的对 3 取模运算呢？二进制中 1 个 bit 最多只能表示 0 和 1，当一个数出现三次时，可以用两个 bit 来表示，每两个 bit 的高位存放在一个 int 中，低位存放在另一个 int 中。用 00 表示 32 位 bit 中的某位未出现过一次（即该位没出现过 1），01 表示该位出现一次，10 表示该位出现两次，当出现三次时重置为 00，出现次数的规律变化为 00 -> 01 -> 10 -> 00，最后的结果就是低位的那个 int。根据这个关系，可以得到一个真值表：
high_bit |
low_bit |
input |
high_bit_output |
low_bit_output |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
如何根据上面的真值表推导出高位和低位的逻辑表达式呢？这需要用到数字电路的知识，有两种方法：
第一种方法：以真值表内输出端“1”为准，1) 从真值表内找出输出端为“1”的各行，把每行的输入变量写成乘积形式，遇到“0”的输入时加上非号；2）把各乘积项相加，即得到逻辑表达式。
第二种方法：以真值表内输出端“0”为准，1) 从真值表内找出输出端为“0”的各行，把每行的输入变量写成求和形式，遇到“1”的输入时加上非号；2）把各求和项相乘，即得到逻辑表达式。
现在先推导 low_bit_output 的逻辑表达式，以 high_bit、low_bit、input 作为输入，输出端为“1”的只有两行，使用第一种方法：
low_bit_output = ~hight_bit & low_bit & ~input + ~hight_bit & ~low_bit & input
= ~hight_bit & (low_bit & ~input + ~low_bit & input)
= ~hight_bit & (low_bit ^ input)
再推导 high_bit_output 的逻辑表达式，这里需要注意的是，如果也以 high_bit、low_bit、input 作为输入的话，在计算 low_bit_output 前需要用临时变量保存 low_bit，不然计算完 low_bit_output 后 �low_bit 已经改变了。另一种不用临时变量的方式就是以 high_bit、low_bit_output、input 作为输入：
high_bit_output = high_bit & ~input & ~low_bit_output + ~high_bit & input & ~low_bit_output
= ~low_bit_output & (high_bit & ~input + ~high_bit & input)
= ~low_bit_output & (high_bit ^ input)
根据上面两个逻辑表达式，就很容易得出下面这种解法，时间复杂度�只有 O(N)：
// 其他元素都出现三次
public int singleNumber(int[] nums) {
int low = 0, high = 0;
for (int n : nums) {
low = ~high & (low ^ n);
high = ~low & (high ^ n);
}
return low;
}
这种利用真值表推导的方法具有非常好的扩展性，如果求一个只�出现两次的数，只需要返回 high 即可，而且对于�其他所有数都出现五次或者七次也可以用这种方式解决，只需要增加输入位数即可。
10. 找出数组中只出现一次的数扩展：有两个数只出现一次
LeetCode 260. Single Number III
题目描述：数组中所有的数都出现两次，只有两个数只出现一次，要求在线性时间复杂度内完成。
分析：假设两个只出现一次数为 x 和 y，继续利用 n ^ n = 0 的特点，所有元素异或的结果为 x ^ y。如何找出 x 和 y 呢，�可以根据 x 和 y 某一位 bit 不同把数组分为两个子数组，x 和 y 分别在两个子数组，其他成对出现的元素要么两个都在 x 所在的数组，要么两个都在 y �所在的�数组，这样就转化为一开始的问题了。
// 其他元素都出现两次，只有两个�元素出现一次
public int[] singleNumber(int[] nums) {
// first, get diff = x ^ y
int diff = 0;
for (int num : nums) {
diff ^= num;
}
// second, get the last 1 bit, mean the last bit a diff b
diff &= -diff;
int[] result = {0, 0};
// divide array to two group
for (int num : nums) {
if ((num & diff) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
11. 求数组中两个整数最大的异或结果
LeetCode 421. Maximum XOR of Two Numbers in an Array
题目描述：给定一个非空数组，里面的元素都是非负整数，在 O(N) 时间内求数组中两个元素最大的异或结果。
分析：�正常思路很难在 O(N) 时间内完成，这时可以考虑���分成 32 位 bit 来考虑，题目是求最大的异或结果，可以从结果的高位算起，从低到高的第 32 位肯定为 0，表示为�非负数。那么怎么知道第 31 位是否为 1 呢？假设�最大的异或结果的第 31 位是否为 1，那么数组中肯定有两个数的异或结果的第 31 位是否为 1，根据 t = a ^ b, b = a ^ t 的特点，如果�数组存在一个数 a，�而且 a ^ t 也在数组，说明存在两个数异或后在第 31 位为 1，那么最大的异或结果的在第 31 位为 1。然后�判断第 30 位，这时要加上第 31 位的结果，循环直到第 1 位。时间复杂度为 O(31N)，也相当于 O(N)。
// 求数组两个数最大异或结果
public int findMaximumXOR(int[] nums) {
if (nums.length < 2) {
return 0;
}
int max = 0, mask = 0;
for (int i = 30; i >= 0; i --) {
mask |= 1 << i;
Set<Integer> set = new HashSet<>();
// 提取数组的前缀
for (int n : nums) {
set.add(n & mask);
}
int t = max | (1 << i);
// 如果 t = a ^ b, b = t ^ a 一定在 sets 中
for (int prefix : set) {
if (set.contains(t ^ prefix)) {
max = t;
break;
}
}
}
return max;
}
12. 总结
仔细思考上面 11 道位操作的算法题后，我总结出下面一些特点，牢记这些特点以后遇到位操作的算法题后就每那么难了：
-
整数在计算机中是以 32 位二进制表示的，可以把 32 位拆分开思考问题，上面很多的题目都利用了这种思想。
-
对于单个整数的操作，例如 bitCount、reverseBit，可以采用二分法，简化问题。
-
n & (n - 1)可以消除 n 中最后一位 1 bit，n & (- n)可以得到最后一位 1 bit。 -
n ^ n = 0，这个特点可以消除重复出现的数。 -
可以利用数字电路的知识，用真值表推导逻辑表达式，Single Number II 的最后一种解法非常值得借鉴。
-
异或运算符有个特点
t = a ^ b, b = a ^ t。
参考文章：
网友评论