LeetCode 位运算
位运算
基本原理
0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
1、利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；
2、利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
1^1^2 = 2
3、利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
01011011 &
00111100
--------
00011000
4、利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。
01011011 |
00111100
--------
01111111
位与运算技巧
1、n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。
01011011 &
01011010
--------
01011010
2、n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
10110100 &
01001100
--------
00000100
移位运算
>> n 为算术右移，相当于除以 2n，例如 -7 >> 2 = -2。
11111111111111111111111111111001 >> 2
--------
11111111111111111111111111111110
>>> n 为无符号右移，左边会补上 0。例如 -7 >>> 2 = 1073741822。
11111111111111111111111111111001 >>> 2
--------
00111111111111111111111111111111
<< n 为算术左移，相当于乘以 2n。-7 << 2 = -28。
11111111111111111111111111111001 << 2
--------
11111111111111111111111111100100
mask 计算
要获取 111111111，将 0 取反即可，~0。
要得到只有第 i 位为 1 的 mask，将 1 向左移动 i-1 位即可，1<<(i-1) 。例如 1<<4 得到只有第 5 位为 1 的 mask ：00010000。
要得到 1 到 i 位为 1 的 mask，(1<<i)-1 即可，例如将 (1<<4)-1 = 00010000-1 = 00001111。
要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~((1<<i)-1)。
Java 中的位操作
static int Integer.bitCount(); // 统计 1 的数量
static int Integer.highestOneBit(); // 获得最高位
static String toBinaryString(int i); // 转换为二进制表示的字符串
剑指 11.二进制中 1 的个数
输入一个整数，输出该数 32 位二进制表示中 1 的个数。其中负数用补码表示。
思路：
把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
count++;
n = n&(n-1);
}
return count;
}
}
1.统计两个数的二进制表示有多少位不同
461.两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
思路：
异或后统计 1 的个数。
1、使用 n&（n-1）
class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y;
int count = 0;
while(z != 0){
count++;
z = z&(z-1);
};
return count;
}
}
2、使用 Java 的方法
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
2. 数组中唯一一个不重复的元素
136.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
思路：
重复的数字异或为 0，0 异或一个数等于他本身，则所有数字异或后等于那个元素。
1 ^ 1 ^ 2 = 2
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int num : nums){
result ^= num;
}
return result;
}
}
3. 找出数组中缺失的那个数
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
输入: [3,0,1]
输出: 2
思路：
将这些数字和 0-n 所有数字异或。得到的就是缺少的数。因为除了缺少的数，其他数值都是重复的。
class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for(int i = 0; i < nums.length; i++){
result ^= i ^ nums[i];
}
return result ^ nums.length;
}
}
4. 数组中不重复的两个元素
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
输入: [1,2,1,3,2,5]
输出: [3,5]
思路：
diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
class Solution {
public int[] singleNumber(int[] nums) {
int diff = 0;
for(int num : nums) diff ^= num;
diff &= -diff;
int[] result = new int[2];
for(int num : nums){
if((num & diff) == 0) result[0] ^= num;
else result[1] ^= num;
}
return result;
}
}
5. 翻转一个数的比特位
190.颠倒给定的 32 位无符号整数的二进制位。
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
思路：
将 n 从右向左取位加入另一个数中。
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int result = 0;
for(int i = 0; i < 32; i++){
result <<= 1;//result 算术左移
result |= (n&1);//n&1 取 n 最右位，result| 将该位赋予 result 右位上
n >>>= 1;//n 无符号右移，消除已经获取的最右位，左边填 0
}
return result;
}
}
6. 不用额外变量交换两个整数
a = a ^ b;
b = a ^ b;
a = a ^ b;
7. 判断一个数是不是 2 的 n 次方
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
思路：
二进制中应只有一个一，且必须大于 0
class Solution {
public boolean isPowerOfTwo(int n) {
return n>0 && Integer.bitCount(n) == 1;
}
}
因为只有一个 1，所以消除 1 后为 0.
class Solution {
public boolean isPowerOfTwo(int n) {
return n>0 && (n&(n-1))==0;
}
}
8. 判断一个数是不是 4 的 n 次方
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
思路：
大于 0，只能在奇数位有一个 1。则在判断只有一个 1 的基础上再判断是否在奇数位上。
class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num-1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
}
}
9. 判断一个数的位级表示是否不会出现连续的 0 和 1
给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
思路：
对于 1010 这种位级表示的数，把它向右移动 1 位得到 101，这两个数每个位都不同，因此异或得到的结果为 1111。
class Solution {
public boolean hasAlternatingBits(int n) {
n = n ^ (n >> 1);
return (n & (n+1)) == 0;
}
}
10. 求一个数的补码
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
不考虑二进制表示中的首 0 部分。
思路：
对于 00000101，要求补码可以将它与 00000111 进行异或操作。那么问题就转换为求掩码 00000111。
class Solution {
public int findComplement(int num) {
int mask = 1<<30;
while((mask & num) == 0) mask >>= 1;
return num ^ ((mask<<1)-1);
}
}
11. 实现整数的加法
371.不使用运算符 + 和 - ，计算两整数 a 、b 之和。
思路：
a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位，最终结果为这两数相加。
class Solution {
public int getSum(int a, int b) {
int result = 0;
int carry = 1;
while(carry != 0){
result = a ^ b;
carry = (a&b)<<1;
a = result;
b = carry;
}
return result;
}
}
12. 字符串数组最大乘积
318.给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
13. 统计从 0 ~ n 每个数的二进制表示中 1 的个数
338.给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
思路：
对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;
class Solution {
public int[] countBits(int num) {
int result[] = new int[num+1];
for(int i = 1; i<=num; i++){
result[i] = result[i&(i-1)] + 1;
}
return result;
}
}如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
上一篇： LeetCode 算法之分治
下一篇： 谈谈自己对于 AOP 的了解
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论