位运算
- 1.常用技巧
- 2.位运算基础问题
- （1）汉明距离(461)
- （2）颠倒二进制位(190)
- （3）只出现一次的数字(136)
- 3.二进制特性
- （1）4的幂(342)
- （2）大单词长度乘积(318)
- （3）比特位计数(338)
- 4.练习
- （1）丢失的数字(268)
- （2）交替位二进制数(693)
- （3）数字的补数(476)
- （4）只出现一次的数字 III(260)
创新互联公司服务电话：028-86922220，为您提供成都网站建设网页设计及定制高端网站建设服务，
创新互联公司网页制作领域10余年，包括
成都会所设计等多个行业拥有丰富的网站推广经验，选择
创新互联公司，为企业保驾护航！1.常用技巧
（1）位运算符号：^ 按位异或(相等为0,不等为1) & 按位与 | 按位或
~ 取反<< 算数左移 >>算术右移
（2）运算特性：x ^ 0 = x x & 0 = 0 x | 0 = x
x ^ 1 = ~x x & 1 = x x | 1 = 1
x ^ x = 0 x & x = x x | x = x
（3）技巧：n&(n-1)可以去除n的位级表示中最低的那一位 例如：11110100 减去1得到11110011，他两按位与得到
11110000
n&(-n)可以得到n的位级表示中最低的那一位 例如：11110100 取负得到00001100，他两按位与得到
00000100
2.位运算基础问题
（1）汉明距离(461)
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
输入：x = 3, y = 1
输出：1
//移位运算
public class Solution {public static void main(String[] args) {int x=3;
int y=1;
Solution solution=new Solution();
System.out.println(solution.hammingDistance(x,y));
}
public int hammingDistance(int x, int y) {//如果两数相等 汉明距离为0
if (x==y){return 0;
}
//求两个数相异或的结果 两数之间的汉明距离其实就是两个数相异或的结果对应的二进制有多少个1
int red=x^y;
int count=0;//汉明距离
while (red>0){//如果当前red和1相与为1 证明当前red二进制数的最低为为1
if ((red&1)==1){count++;
}
red=red>>1;//red右移一位
}
return count;
}
}
//使用内置函数
public class Solution {public static void main(String[] args) {int x=3;
int y=1;
Solution solution=new Solution();
System.out.println(solution.hammingDistance(x,y));
}
public int hammingDistance(int x, int y) {//直接使用内置函数 求一个数二进制中1的数量
return Integer.bitCount(x^y);
}
}
（2）颠倒二进制位(190)
颠倒给定的 32 位无符号整数的二进制位。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
public class Solution {public static void main(String[] args) {int n=111;
Solution solution=new Solution();
System.out.println(solution.reverseBits(n));
}
public int reverseBits(int n) {int res=0;//输出的数
//逐位颠倒
for (int i=0;i<32&&n!=0;i++){//n&1求出n的最低位的数字 然后将其左移31-i位 得到的结果与res按位或(可以实现相加)
//按位或也可以用 + res+=(n&1)<<(31-i); 但是需要占用更多的空间
res|=(n&1)<<(31-i);
n>>>=1;//n右移一位
}
return res;
}
}
（3）只出现一次的数字(136)
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
输入：nums = [2,2,1]
输出：1
输入：nums = [4,1,2,1,2]
输出：4
输入：nums = [1]
输出：1
public class Solution {public static void main(String[] args) {int[] arr={4,1,2,1,2};
Solution solution=new Solution();
System.out.println(solution.singleNumber(arr));
}
public int singleNumber(int[] nums) {int n=nums.length;
if (n==1){return nums[0];
}
int num=0;//只出现了一次的数
//遍历数组 使用异或 出现两次的元素异或为0 最后得出的结果就是那个单独的元素
for (int i=0;inum^=nums[i];
}
return num;
}
}
3.二进制特性
（1）4的幂(342)
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
输入：n = 16
输出：true
输入：n = 5
输出：false
输入：n = 1
输出：true
//使用循环
public class Solution {public static void main(String[] args) {int n=16;
Solution solution=new Solution();
System.out.println(solution.isPowerOfFour(n));
}
public boolean isPowerOfFour(int n) {//首先排除负数和除1以外的奇数
if (n<=0){return false;
}
if (n%2!=0&&n>1){return false;
}
while (n>0){if (n==1){return true;
} else if (n%4!=0) {return false;
}
n/=4;
}
return true;
}
}
//使用位运算 比使用循环慢
public class Solution {public static void main(String[] args) {int n=16;
Solution solution=new Solution();
System.out.println(solution.isPowerOfFour(n));
}
public boolean isPowerOfFour(int n) {return n>0&&(n&(n-1))==0&&(n&0xaaaaaaaa)==0;
}
}
//取模性质 效率最高
//4的幂对3取模==1
public class Solution {public static void main(String[] args) {int n=16;
Solution solution=new Solution();
System.out.println(solution.isPowerOfFour(n));
}
public boolean isPowerOfFour(int n) {return n>0&&n%3==1;
}
}
（2）大单词长度乘积(318)
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。
输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4
解释：这两个单词为 "ab", "cd"。
输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。
public class Solution {public static void main(String[] args) {String[] s={"abcw","baz","foo","bar","xtfn","abcdef"};
Solution solution=new Solution();
System.out.println(solution.maxProduct(s));
}
public int maxProduct(String[] words) {int n= words.length;
int[] masks=new int[n];//记录每个单词的掩码位 26个字母每个字母对应一位
int max=0;//大值
for (int i=0;iString word=words[i];
//计算每个单词对应的字符所在的二进制位置
for (int j=0;j//这里使用 | 而不是 + 是为了避免多个相同字符影响
masks[i]|=1<<(word.charAt(j)-'a');
}
}
for (int i=0;ifor (int j=1;j//(masks[i]&masks[j])==0 表示两个单词没有重复元素
if ((masks[i]&masks[j])==0){max=Math.max(max,words[i].length()*words[j].length());
}
}
}
return max;
}
}
（3）比特位计数(338)
给你一个整数 n ，对于 0<= i<= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案
输入：n = 2
输出：[0,1,1]
解释：
0 -->0
1 -->1
2 -->10
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 -->0
1 -->1
2 -->10
3 -->11
4 -->100
5 -->101
public class Solution {public static void main(String[] args) {int n=5;
Solution solution=new Solution();
int[] bits = solution.countBits(n);
for (int i=0;i< bits.length;i++){System.out.print(bits[i]+" ");
}
}
public int[] countBits(int n) {int[] arr=new int[n+1];
for (int i=1;i<=n;i++){int count=0;
int j=i;
while (j>0){if ((j&1)==1){count++;
}
j=j>>1;
}
arr[i]=count;
}
return arr;
}
}
//动态规划+位运算
public class Solution {public static void main(String[] args) {int n=5;
Solution solution=new Solution();
int[] bits = solution.countBits(n);
for (int i=0;i< bits.length;i++){System.out.print(bits[i]+" ");
}
}
public int[] countBits(int n) {int[] arr=new int[n+1];
int highBit=0;
for (int i=1;i<=n;i++){if ((i&(i-1))==0){highBit=i;
}
arr[i]=arr[i-highBit]+1;
}
return arr;
}
}
4.练习
（1）丢失的数字(268)
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
public class Solution {public static void main(String[] args) {int[] arr={9,6,4,2,3,5,7,0,1};
Solution solution=new Solution();
System.out.println(solution.missingNumber(arr));
}
public int missingNumber(int[] nums) {int n=nums.length;
int total=n*(n+1)/2;//1~n所有数的和
int numsAll=0;//数组中所有数的和
for (int i=0;inumsAll+=nums[i];
}
//没有出现的那个数就是总和减去数组中所有数的和
return total-numsAll;
}
}
（2）交替位二进制数(693)
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
输入：n = 5
输出：true
解释：5 的二进制表示是：101
输入：n = 7
输出：false
解释：7 的二进制表示是：111.
输入：n = 11
输出：false
解释：11 的二进制表示是：1011.
如果一个二进制n是0 1 交替出现的，那么n^(n>>1)得到的数全为1，可以根据这个进行判断
public class Solution {public static void main(String[] args) {int n=11;
Solution solution=new Solution();
System.out.println(solution.hasAlternatingBits(n));
}
public boolean hasAlternatingBits(int n) {int x=n^(n>>1);
while (x>0){if ((x&1)!=1){return false;
}
x=x>>1;
}
return true;
}
}
（3）数字的补数(476)
对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。
给你一个整数 num ，输出它的补数。
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
因为计算机中整数是32为存储的，不只是存储有效二进制位，所以我们需要找到num二进制最高位的1，然后对1以及更低
的位进行取反
public class Solution {public static void main(String[] args) {int n=5;
Solution solution=new Solution();
System.out.println(solution.findComplement(n));
}
public int findComplement(int num) {int high=0;//num的最高位1在第几位
//最高位31位为符号位 不能取到
for (int i=1;i<=30;i++){if (num>=(1<high=i;
}else {break;
}
}
int temp=1;
if (high==30){temp=0x7fffffff;
}else {temp=(temp<<(high+1))-1;
}
//一个数异或和它位数相同的全为1的数 就是给他取反
return num^temp;
}
}
（4）只出现一次的数字 III(260)
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
输入：nums = [-1,0]
输出：[-1,0]
输入：nums = [0,1]
输出：[1,0]
//哈希表
public class Solution {public static void main(String[] args) {int[] arr={1,2,1,3,2,5};
Solution solution=new Solution();
int[] number = solution.singleNumber(arr);
for (int i=0;i<2;i++){System.out.print(number[i]+" ");
}
}
public int[] singleNumber(int[] nums) {int n= nums.length;
if (n==2){return nums;
}
int[] arr=new int[2];
Mapmap=new HashMap<>();//用来存储数字和出现的次数
Listlist=new ArrayList<>(2);//用来保存出现一次的数字
for (int i=0;iif (map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])+1);
}else {map.put(nums[i],1);
}
}
for (Map.Entryentry: map.entrySet()){//如果出现的次数不为2 就将key加入list集合
if (entry.getValue()!=2){list.add(entry.getKey());
}
}
for (int i=0;i<2;i++){arr[i]=list.get(i);
}
return arr;
}
}
//位运算
public class Solution {public static void main(String[] args) {int[] arr={1,2,1,3,2,5};
Solution solution=new Solution();
int[] number = solution.singleNumber(arr);
for (int i=0;i<2;i++){System.out.print(number[i]+" ");
}
}
public int[] singleNumber(int[] nums) {int n= nums.length;
if (n==2){return nums;
}
int[] arr;
int xor=0;//异或和 因为其他数都重复出现 所以异或和就是单独出现的两数的异或和
for (int i=0;ixor^=nums[i];
}
//xor&(-xor) 可以求出xor最低位的那一位1该位置记为low 则单独出现的两数的第low位一定一个为1一个为0
//这样就可以将数组中的数分为两类 一类第low位为1 一类第low位为0
int low=xor&(-xor);
int num1=0;
int num2=0;
for (int i=0;iif ((nums[i]&low)!=0){num1^=nums[i];
}else {num2^=nums[i];
}
}
arr=new int[]{num1,num2};
return arr;
}
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享标题：leetcode--位运算-创新互联
文章出自：
http://cdkjz.cn/article/egopd.html
