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};}
}