优选算法-常见位运算总结
1.基础位运算：
>> :右移运算符：
-
逻辑右移（无符号数）：高位补 0，低位直接丢弃。
示例：8 >> 2（二进制1000右移 2 位）结果为0010（十进制 2）。 -
算术右移（有符号数）：高位补符号位（正数补 0，负数补 1），低位丢弃。
-
示例：
-8 >> 2（假设 8 位二进制11111000右移 2 位）结果为11111110（十进制 -2） -
应用场景
- 快速除以 2 的幂次。x>>n等价于：x/(2^n)
<<:左移运算符:
将一个数的二进制表示向左移动指定的位数，右侧空出的位用 0 填充。
x<<n,等价于 (x) 乘以 2 的 (n) 次方。
&:按位与：同1为1，有0为0.
|：按位或：有1为1，同0为0.
^:异或：相同为0，相异为1；无进位相加。
2.求一个数x的二进制位的第n 位是0还是1（最右侧为第0位）：
(x>n)&1
3.将一个数x的二进制的第n位改成1（最右侧为第0位）：
(1<<n) | x
4.将一个数x的二进制的第n位改成0（最右侧为第0位）：
~(1<<n) | x
5.位图的思想：
使用int的二进制位32位：0~31，每一位有两种状态0,1.分别表示不同的含义。
6.获取一个数x的二进制位的最右侧的1： 1100 -> 0100
x&(-x)
-x:将x的最右侧的1的左侧的二进制都取反，1右侧保持不变；
x:1100 -x:0100
x&(-x)得到的就是1和1左边的二进制数，而1又是最右侧的，就得到了最右侧的1
7.删除一个数x的二进制位的最右侧的1：1100 -> 1000
x&(x-1)
x-1：将x的最右侧的1(包含该位）的右侧的二进制都取反，1左侧保持不变
x:1100 x-1: 1011
按位与后得就是删除最右侧1的效果。
8.位运算优先级
记不住就加括号
9.异或运算（^）的运算定律：
a^0 = a
a^a = 0(消消乐）
a^b^c = a^(b^c)
练习题：
136. 只出现一次的数字 - 力扣（LeetCode）
class Solution {public int singleNumber(int[] nums) {int n = nums.length;int ret = 0;for(int i=0;i<n;i++){//a^a = 0//a^0 = aret^=nums[i];}return ret;}
}260. 只出现一次的数字 III - 力扣（LeetCode）
class Solution {public int[] singleNumber(int[] nums) {int ret=0;// 将数组中所有元素进行异或运算,最终结果中保存的就是那两个不同的数x1,x2 的异或结果for(int i=0;i<nums.length;i++){ret^=nums[i];}// 先找出最低位为1的位置,之所以为1,是因为x1,和x2的这一位的二进制位是不相同的,异或后才会是1int tmp=ret&(-ret);//获取到最低位为1的值// 可以将数组分成两部分: tmp位为1,tmp位为0int x1=0;//tmp位为0int x2=0;//tmp位为1// 将所有元素与tmp进行&运算://结果不为0的一组进行^运算，结果为0的进行^运算//（相同元素^运算，会相互抵消a^a=0,得到的就是那个只出现一侧的元素）,for(int i=0;i<nums.length;i++){if((tmp&nums[i] )==0 ) x1^=nums[i];else x2^=nums[i];}return new int[]{x1,x2};}
}191. 位1的个数 - 力扣（LeetCode）
class Solution {public int hammingWeight(int n) {int ret = 0;while(n!=0){if((n & 1)==1) ret++;n>>=1;}return ret;}
}338. 比特位计数 - 力扣（LeetCode）
class Solution {public int[] countBits(int n) {int[] ret = new int[n+1];for(int i=0;i<=n;i++){int t = 0;for(int j=0;j<32;j++){if(((i>>j)&1)==1) t++;}ret[i] = t;}return ret;}
}461. 汉明距离 - 力扣（LeetCode）
class Solution {public int hammingDistance(int x, int y) {int ret=0;for(int i=0;i<32;i++){// 获取最低位的二进制位int m=(x>>i)&1;int n=(y>>i)&1;if(m!=n) ret++;}return ret;}
}371. 两整数之和 - 力扣（LeetCode）
class Solution {public int getSum(int a, int b) {//^ :无进位相加// &: 保存进位值// int a=a^b;// int b=(a&b)<<1;while(b!=0){int a1=a^b;int b1=(a&b)<<1;//(a&b)记录当前为是否需要进位，<<1:得到进位值a=a1;b=b1;}//b=0时，说明不需要进位了，a中保留的就是结果return a;}
}137. 只出现一次的数字 II - 力扣（LeetCode）
统计每个数的第i二进制位为1的个数,然后%3,当不为0时,说明该二进制位的1是要求的数的二进制位累计的,将结果的该为置1.以次计算32位.得到结果
class Solution {public int singleNumber(int[] nums) {// 位运算解决int log=0;for(int i=0;i<32;i++){int ret=0; //注意:ret每次计算都要复原for(int j=0;j<nums.length;j++){ret+=((nums[j]>>i)&1);//获取所有元素二进制第i位的和// if(((nums[j]>>i) & 1)==1) ret++; }ret%=3;if(ret==1) log|=(1<<i);}return log;}
}面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
260题的改版
class Solution {public int[] missingTwo(int[] nums) {int ret=0;for(int i=0;i<nums.length;i++){ret^=nums[i];ret^=(i+1);}int n=nums.length;ret^=(n+1);ret^=(n+2);//找到二进制中最低位的1的位置,从而将数组分成两类int tmp = ret&(-ret);int x1=0;int x2=0;for(int i=0;i<nums.length;i++){if((tmp&nums[i])==0) x1^=nums[i];else x2^=nums[i];}for(int i=1;i<=n+2;i++){if((tmp&i)==0) x1^=i;else x2^=i;}return new int[]{x1,x2};}
}