📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

---

位運算操作總結

第x位：從0下標開始的

1. 基礎位運算
   • 右移：>>、左移：<<、取反：~、按位與（邏輯與）：&、按位或（邏輯或）：|、按位異或^（相同為0，相異為1）
2. 給定一個數 (n)，確定它的二進制表示中的第 x 位是0還是1
   • (n >> x) & 1 ，或者：n & $2^x$（$2^x$也就是(1 << x)）
3. 將一個數 (n) 的二進制表示的第 x 位修改成 1
   • n |= (1 << x)
4. 將一個數 (n) 的二進制表示的第x位修改成 0
   • n &= (~(1 << x))
5. 位圖的思想【1 - 4 通常為位圖服務】
   • 本質：哈希表
   • 用變量的bit位（0 / 1）記錄信息：int有32個bit位
6. 提取一個數 (n)二進制表示中最右側的 1
   • n & (- n)
   • 為什么正確？因為：(-n) 的補碼求法：在 n 的補碼上：從右向左找到第一個 1 ，這個 1 左邊的數全部取反（包括符號位）
7. 干掉一個數 (n) 二進制表示中最右側的 1（1 變 0）
   • n &= (n - 1)
   • 為什么正確：因為：(n - 1)的值：在 n 的補碼上，最右側的 1 變 0 ，然后 1 右邊的 0 變 1
8. 位運算的優先級
   • 能加括號就加括號
9. 異或(^)運算的運算律
   • a ^ 0 = a
   • a ^ a = 0
   • a ^ b ^ c = a ^ (b ^ c)，即：符合交換律和結合律

下面這些題目主要用于鞏固上面的知識：

191. 位 1 的個數

題目鏈接：https://leetcode.cn/problems/number-of-1-bits/description/

class Solution {
public:int hammingWeight(int n) {int ans = 0;for(int i = 0; i < 32; i++){if((n >> i) & 1)ans++;}return ans;}
};

• 如果我們想要依次得到一個int變量的每一位，可以for(int i = 0; i < 32; i++)，然后每次讓變量>> i

---

338. 比特位計數

題目鏈接：https://leetcode.cn/problems/counting-bits/description/

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1);for(int i = 0; i <= n; i++){int count = 0, num = i;while(num > 0){num &= (num - 1); // 每次該最低位的 1 count++;}ans[i] = count;}return ans;}
};

---

461. 漢明距離

題目鏈接：https://leetcode.cn/problems/hamming-distance/description/

class Solution {
public:int hammingDistance(int x, int y) {int s = x ^ y, ans = 0;while(s > 0){s &= (s - 1);ans++;}return ans;}
};

---

136. 只出現一次的數字

題目鏈接：https://leetcode.cn/problems/single-number/description/

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = nums[0];for(int i = 1; i < nums.size(); i++)ans ^= nums[i];return ans;}
};

---

260. 只出現一次的數字 III

題目鏈接：https://leetcode.cn/problems/single-number-iii/description/

思路：
設答案為 a 和 b

• 想辦法把兩個數 a, b 分開，分成兩組
• 所有數異或的結果 s == a ^ b
• 那么，s 的二進制位中為 1 的那一位，對于其他數：該位同為 1 / 0，相異以后得到 0
• 但是對于 a 和 b 肯定是 一 1 一 0 才得到的 1
• 于是可以根據 1 這一位，把原來的數組分成兩組
• 再分別對組內的數進行全部異或，就可以得到 a 和 b

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unsigned int s = 0;for(auto x: nums)s ^= x;unsigned int lowbit = s &= (-s); // 獲取最低位的 1int a = 0, b = 0;for(auto x: nums){if((x & lowbit))a ^= x;elseb ^= x;}return {a, b};}
};

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！