前提知識：
- <<表示左移移，不分正負數(shù)，低位補0；
- >>表示右移，如果該數(shù)為正，則高位補0，若為負數(shù)，則高位補1；
- >>>表示無符號右移，也叫邏輯右移，即若該數(shù)為正，則高位補0，而若該數(shù)為負數(shù)，則右移后高位同樣補0
異或運算性質(zhì)：
- 任何數(shù)和 0 做異或運算，結(jié)果仍然是原來的數(shù)，即 a ⊕ 0 = a。
- 任何數(shù)和其自身做異或運算，結(jié)果是 0，即 a ⊕ a = 0
- 異或運算滿足交換律和結(jié)合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
231. 2 的冪
題解1：首先想到的是判斷這個數(shù)是否為偶數(shù)，如果是偶數(shù)，就一直除以2 ， 直到是奇數(shù)為止， 最后在判斷這個奇數(shù)是否等于1，但是會發(fā)現(xiàn)超過時間限制，所以我們換一種思路， 其實n 就只能是1 ，2 ， 4 ， 8 ， 1 6 … … 這樣的數(shù)字，他們都有一個特點，二進制位中只有一個1，也就是說滿足這個條件，那么這個數(shù)肯定是2 的冪次方。
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0){
return false;
}
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n >>> i) & 1) == 1){
count++;
}
}
return count == 1;
}
}
題解2：劍指 Offer 15. 二進制中1的個數(shù)中通過(n & (n-1))可以消去二進制位中最右邊的1，如果n 的二進制位中只有一個1 ， 那么n & ( n - 1 ) 的結(jié)果肯定是0 ， 所以我們只需要判斷n 大于0 的時候， n & ( n - 1 ) 是否等于0 即可， 一行代碼搞定。
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0){
return false;
}
return (n & (n-1)) == 0;
}
}
題解3：n 和- n 在二進制位中的區(qū)別， 因為- n 是n 每一個都取反然后再加上1 的結(jié)果， 所以n 和- n 的區(qū)別就是n 原來右邊第一個1 以及他右邊的都不變，所以在確定n大于0的情況下，只需要判斷(n&-n)==n即可，也是一行代碼搞定。
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
}
劍指 Offer 15. 二進制中1的個數(shù)
題解：18種解法，這個帖子講了18種解法。列出常用的兩種：
題解1：把n往右移32次，每次都和1進行與運算
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n >>> i) & 1) == 1) {
count++;
}
}
return count;
}
題解2：這個是最常見的，每次消去最右邊的1，直到消完為止
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
136. 只出現(xiàn)一次的數(shù)字
異或運算性質(zhì)：
- 任何數(shù)和 0 做異或運算，結(jié)果仍然是原來的數(shù)，即 a ⊕ 0 = a。
- 任何數(shù)和其自身做異或運算，結(jié)果是 0，即 a ⊕ a = 0
- 異或運算滿足交換律和結(jié)合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
260. 只出現(xiàn)一次的數(shù)字 III
該題滑動窗口專題有講解，本專題位運算解法。
位運算，異或運算有性質(zhì)如下：
- 任何數(shù)和 0 做異或運算，結(jié)果仍然是原來的數(shù)，即 a ⊕ 0 = a。
- 任何數(shù)和其自身做異或運算，結(jié)果是 0，即 a ⊕ a = 0
- 異或運算滿足交換律和結(jié)合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
題解：基于位運算性質(zhì)
- 先將數(shù)組的所有元素異或得到的一個結(jié)果，這個結(jié)果為不存在重復(fù)的兩個元素異或的結(jié)果，因為相同的都已經(jīng)抵消掉了，同時也不為0，因為這兩個元素是不同的。
- 然后我們需要將來數(shù)組分為兩組，一組包含其中一個我們需要的結(jié)果，另外一組包含另外一個我們需要的結(jié)果，同時相同的元素必須分到一組，這樣，我們對每一組的所有元素分別進行異或，就可以在每一組中得到一個我們想要的結(jié)果，怎么做呢？
- lab &= ?lab得到出 lab最右側(cè)的1,因為異或值為1，說明我們需要的兩個值里面其中一個為0，另外一個為1，這樣才能異或為1
- 然后遍歷，分組，每一組分別異或就可以了
class Solution {
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
int lab = 0;
for(int num : nums){
lab ^= num;
}
lab &= -lab;
for(int num : nums){
if ((num & lab) != 0){
res[0] ^= num;
}else {
res[1] ^= num;
}
}
return res;
}
}
劍指 Offer II 004. 只出現(xiàn)一次的數(shù)字
137. 只出現(xiàn)一次的數(shù)字 II
題解：在java中int類型是32位，我們需要統(tǒng)計所有數(shù)字在某一位置的和能不能被3整除，如果不能被3整除，說明那個只出現(xiàn)一次的數(shù)字的二進制在那個位置是1……把32位全部統(tǒng)計完為止。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
if (oneCount % 3 != 0){
res |= 1 << i;//按位或，給相應(yīng)的位置賦1
}
}
return res;
}
}
位運算部分小結(jié)
類似的題：136. 只出現(xiàn)一次的數(shù)字、260. 只出現(xiàn)一次的數(shù)字 III、劍指 Offer II 004. 只出現(xiàn)一次的數(shù)字
一，如果只有一個數(shù)字出現(xiàn)一次，其他數(shù)字都出現(xiàn)偶數(shù)次，我們只需要把所有數(shù)字異或一遍即可。例如：136題目Leetcode連接
因為異或有下面幾條性質(zhì)
- a^a=0 任何數(shù)字和自己異或結(jié)果是0
- a^0=a 任何數(shù)字和0異或還是他自己
- abc=acb 異或運算具有交換律
二，如果只有一個數(shù)字出現(xiàn)一次，其他數(shù)字都出現(xiàn)奇數(shù)次，我們可以用下面代碼來解決。例如：劍指 Offer II 004. 只出現(xiàn)一次的數(shù)字
class Solution {
public int singleNumber(int[] nums,int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
if (oneCount % n != 0){
res |= 1 << i;//按位或，給相應(yīng)的位置賦1
}
}
return res;
}
}
劍指 Offer 53 - II. 0～n-1中缺失的數(shù)字
題解：把所有數(shù)字都跟自己對應(yīng)的下標(biāo)異或，最后將結(jié)果與長度異或就可以得到結(jié)果，因為如果是正常順序的話，所有數(shù)字都跟自己對應(yīng)的下標(biāo)相等，異或后結(jié)果為0，最后與長度異或就可以得到最終的結(jié)果，以[0,1,2,3,4,5,6,7,9]為例，異或到最后一個數(shù)字時res=98,然后異或長度9，即res=98^9=8。
異或性質(zhì)：
- a^a=0 任何數(shù)字和自己異或結(jié)果是0
- a^0=a 任何數(shù)字和0異或還是他自己
- abc=acb 異或運算具有交換律
class Solution {
public int missingNumber(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
res ^= nums[i] ^ i;
}
return res ^ nums.length;
}
}
389. 找不同
題解一：與136. 只出現(xiàn)一次的數(shù)字幾乎一模一樣的題目。
class Solution {
public char findTheDifference(String s, String t) {
char res = 0;
String str = s + t;
for (int i = 0; i < str.length(); i++) {
res ^= str.charAt(i);
}
return res;
}
}
題解二：既然字符串s 比t 少一個字符， 我們先統(tǒng)計字符串s 中每個字符的數(shù)量， 然后減去字符串t中的每個字符， 如果小于0 ， 說明字符串s 比t 少的就是這個字符， 直接返回即可。
class Solution {
public char findTheDifference(String s, String t) {
int[] count = new int[26];
for(int i = 0; i < s.length();i++){
count[s.charAt(i) - 'a']++;
}
for(int i = 0; i < t.length(); i++){
int val = --count[t.charAt(i) - 'a'];
if(val < 0){
return t.charAt(i);
}
}
return 'a';
}
}
題解三：用t 中所有字符的和減去s 中所有字符的和， 最后結(jié)果就是要求的那個字符。
class Solution {
public char findTheDifference(String s, String t) {
char res = 0;
for(int i = 0; i < t.length();i++){
res += t.charAt(i);
}
for(int i = 0; i < s.length(); i++){
res -= s.charAt(i);
}
return res;
}
}
1442. 形成兩個異或相等數(shù)組的三元組數(shù)目
題解：a 的值是數(shù)組[ i … … j - 1 ] 中所有元素的異或結(jié)果， b 的值是數(shù)組[ j … … k ] 中所有元素的異或結(jié)果， 并且a 中異或的元素和b 中異或的元素是連續(xù)的并且沒有重疊。如果要讓a = = b，那么就是a ^ b = 0 ， 也就是arr[i]^arr[i+1]^……^arr[j]^……^arr[k]=0;所以問題就轉(zhuǎn)化成了從數(shù)組a r r 中找到一些連續(xù)的元素， 他們的異或結(jié)果等于0 即可。
i<j，并且j可以等于k，這個k我們不需要管，所以至少需要2個元素。也就是說從數(shù)組arr中找到至少2個以上的連續(xù)的元素他們的異或結(jié)果是0即可成立三元組(i,j,k)。另外連續(xù)n 個元素的異或結(jié)果是0 ， 那么可能的組合就有n - 1 種。這樣就很容易解這道題了。
class Solution {
public int countTriplets(int[] arr) {
int ret = 0;
for (int i = 0; i < arr.length; i++) {
int res = arr[i];
for (int j = i+1; j < arr.length; j++) {
res ^= arr[j];
if (res == 0){
ret += (j-i);
}
}
}
return ret;
}
}
461. 漢明距離
題解：先異或，然后求異或后結(jié)果中1的個數(shù)就行。
class Solution {
public int hammingDistance(int x, int y) {
int res = 0;
int num = x ^ y;
for (int i = 0; i < 32; i++) {
if (((num >>> i) & 1) == 1){
res++;
}
}
return res;
}
}
1356. 根據(jù)數(shù)字二進制下 1 的數(shù)目排序
題解：從題中可以看到0<=arr[i]<=10^4，所以我們可以將原來數(shù)中1的個數(shù)乘100000 + 原來的數(shù)值，然后再排序，排序完后在逐個還原。
class Solution {
public int[] sortByBits(int[] arr) {
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.bitCount(arr[i]) * 100000 + arr[i];
}
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i] % 100000;
}
return arr;
}
}
693. 交替位二進制數(shù)
題解：一個數(shù)的二進制位如果是0和1交替，那么把這個數(shù)往右移一位然后再和原來的數(shù)進行異或運算，就會讓他全部變?yōu)?，然后加上1，那么原來的位置就都變成了0，再跟原來的數(shù)異或，判斷是否為0即可。
class Solution {
public boolean hasAlternatingBits(int n) {
n ^= (n >>> 1);
return (n & (n + 1)) == 0;
}
}
