有關(guān)位運算的操作符

• >>
• <<
• &
• |
• ^
• ~

常見位運算操作

給定一個數(shù)，確定它的二進制中第x位是0還是1

(n >> x) & 1;

將一個數(shù)n的二進制中第x位修改為1

n |= (1 << x)

將一個數(shù)n的二進制中第x位修改為0

n &= (~(1 << x))

提取一個數(shù)二進制中最右側(cè)的1

n & (-n)

去掉一個數(shù)中二進制最右側(cè)的1

n & (n-1)

異或運算律

• a ^ a = 0
• a ^ 0 = a
• a ^ b ^ c = a ^ (b ^ c)

191. 位1的個數(shù) - 力扣（LeetCode）

輸入： n = 00000000000000000000000000001011
輸出： 3
解釋： 輸入的二進制串 00000000000000000000000000001011?中，共有三位為 '1'。

輸入： n = 00000000000000000000000010000000
輸出： 1
解釋： 輸入的二進制串 00000000000000000000000010000000?中，共有一位為 '1'。

輸入： n = 11111111111111111111111111111101
輸出： 31
解釋： 輸入的二進制串 11111111111111111111111111111101 中，共有 31 位為 '1'。

解題思路

n & (n-1)每次可以干掉二進制中最右側(cè)的1

代碼實現(xiàn)

class Solution {
public:int hammingWeight(uint32_t n) {int ret = 0;while(n != 0){n &= n-1;ret++;}return ret;}
};

338. 比特位計數(shù) - 力扣（LeetCode）

輸入： 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

解題思路

利用n&(n-1)從最高位開始統(tǒng)計位1的個數(shù)，將結(jié)果存放到vector中即可。時間復雜度O(n^2)

代碼實現(xiàn)

class Solution 
{
public:vector<int> countBits(int n) {vector<int> ans(n+1);while(n >= 0){int ret = 0,tmp = n;while(tmp != 0){tmp = tmp & (tmp-1);ret++;}ans[n--] = ret;}return ans;}
};

461. 漢明距離 - 力扣（LeetCode）

輸入： x = 1, y = 4
輸出： 2
解釋：
1   (0 0 0 1)
4   (0 1 0 0)

解題思路

異或后求二進制位1的個數(shù)即可

代碼實現(xiàn)

class Solution 
{
public:int hammingDistance(int x, int y) {//異或，求異或后二進制1的個數(shù)即可int ret = x ^ y;int sum = 0;while(ret != 0){   ret &= (ret-1);sum++;}return sum;}
};

136. 只出現(xiàn)一次的數(shù)字 - 力扣（LeetCode）

輸入： nums = [2,2,1]
輸出： 1

輸入： nums = [4,1,2,1,2]
輸出： 4

輸入： nums = [1]
輸出： 1

解題思路

• a^0 = a;
• a^a = 0;
• a^bc = a^(bc)
• 4¹2¹2 = 4⁽¹1)⁽²2)
• 空間復雜度要求O(n) 不能使用哈希表

代碼實現(xiàn)

class Solution 
{
public:int singleNumber(vector<int>& nums) {//a^0 = a;//a^a = 0;//a^b^c = a^(b^c)//4^1^2^1^2 = 4^(1^1)^(2^2)int ret = 0;for(auto &e : nums){ret ^= e;}return ret;}
};

面試題 01.01. 判定字符是否唯一 - 力扣（LeetCode）

輸入: s = "leetcode"
輸出: false 

輸入: s = "abc"
輸出: true

解題思路

• 哈希表。
  • 字符串中僅包含小寫字母，使用數(shù)組模擬哈希表即可。時間復雜度O(n);
• 位運算
  • 位圖思想 26個比特位即可(一個字節(jié)即可)

代碼實現(xiàn)

class Solution 
{
public:bool isUnique(string astr) {if(astr.size() > 26){return false;}//哈希表// int hash[26] = {0};// for(size_t i = 0; i < astr.size(); ++i)// {//     hash[astr[i] - 'a']++;// }// for(auto e : hash)// {//     if(e >= 2 ) return false;// }// return true;// 位圖int bit_map = 0;for(auto e : astr){int index = e - 'a';//判斷是否在位圖中。if((bit_map >> index) & 1 == 1) return false;//加入位圖bit_map |= (1 << index);}return true;}
};

268. 丟失的數(shù)字 - 力扣（LeetCode）

輸入： nums = [3,0,1]
輸出： 2
解釋： n = 3，因為有 3 個數(shù)字，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。

輸入： nums = [0,1]
輸出： 2
解釋： n = 2，因為有 2 個數(shù)字，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。

輸入： nums = [9,6,4,2,3,5,7,0,1]
輸出： 8
解釋： n = 9，因為有 9 個數(shù)字，所以所有的數(shù)字都在范圍 [0,9] 內(nèi)。8 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。

輸入： nums = [0]
輸出： 1
解釋： n = 1，因為有 1 個數(shù)字，所以所有的數(shù)字都在范圍 [0,1] 內(nèi)。1 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。

解題思路

• 哈希表
• 高斯求和
• 異或運算符

class Solution 
{
public:int missingNumber(vector<int>& nums) {//哈希表// int hash[10000] = {0};// //存放到哈希表中// for(size_t i = 0; i < nums.size();++i)// {//     hash[nums[i]]++;// }// //遍歷哈希表// for(size_t i =0 ; i < 10000; i++)// {//     if(hash[i] ==0 ) return i;// }// return 0;//高斯求和// size_t n = nums.size();// int sum = 0;// for(size_t i = 0; i < n ; ++i)// {//     sum += nums[i];// }// return ((n) * (n +1) / 2 ) - sum;//位運算(異或運算律)int ret = 0;for(auto e : nums){ret ^= e;}for(int i = 0; i < nums.size() + 1 ; ++i){ret ^= i;}return ret;}};