歡迎拜訪：霧里看山-CSDN博客
本篇主題：算法思想之位運算(一)
發布時間：2025.4.12
隸屬專欄：算法

滑動窗口算法介紹

位運算（Bit Manipulation）是算法中的高效技巧，通過直接操作二進制位實現快速計算和優化存儲

六大基礎位運算符

運算符	符號	描述	示例
按位與	&	兩數二進制位同為1時結果為1	5 & 3 → 1 (101 & 011 = 001)
按位或	|	任一位為1時結果為1	5 | 3→7 (101 | 011 = 111)
按位異或	^	兩數位不同時結果為1 ，無進位相加	5 ^ 3 → 6 (101 ^ 011 = 110)
按位取反	~	0變1，1變0	~5 → -6（補碼表示）
左移	<<	左移指定位數，低位補0	5 << 1 → 10 (101→1010)
右移	>>	右移指定位數，高位補符號位（算術右移）	-5 >> 1 → -3

常用模板總結

功能	代碼模板
判斷奇偶	x & 1 → 1為奇，0為偶
取最低位的1	x & (-x)
消去最低位的1	x & (x - 1)
異或交換變量	a ^= b; b ^= a; a ^= b;
生成所有子集	for (mask = 0; mask < (1 << n); mask++)
快速冪	右移指數，逐位判斷累乘

例題

位1的個數

題目鏈接

191. 位1的個數

題目描述

給定一個正整數 n，編寫一個函數，獲取一個正整數的二進制形式并返回其二進制表達式中 設置位 的個數（也被稱為漢明重量）。

示例 1：

輸入：n = 11
輸出：3
解釋：輸入的二進制串 1011 中，共有 3 個設置位。

示例 2：

輸入：n = 128
輸出：1
解釋：輸入的二進制串 10000000 中，共有 1 個設置位。

示例 3：

輸入：n = 2147483645
輸出：30
解釋：輸入的二進制串 1111111111111111111111111111101 中，共有 30 個設置位。

提示：

• 1 <= n <= 231 - 1

進階：
如果多次調用這個函數，你將如何優化你的算法？

算法思路

直接使用模板中消去最低位的1，直到變量為零，用一個變量計算次數即可。

代碼實現

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

比特位計數

題目鏈接

338. 比特位計數

題目描述

給你一個整數 n ，對于 0 <= i <= n 中的每個 i ，計算其二進制表示中 1 的個數 ，返回一個長度為 n + 1 的數組 ans 作為答案。

示例 1：

輸入：n = 2
輸出：[0,1,1]
解釋：
0 --> 0
1 --> 1
2 --> 10

示例 2：

輸入：n = 5
輸出：[0,1,1,2,1,2]
解釋：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 105

進階：

• 很容易就能實現時間復雜度為 O(n log n) 的解決方案，你可以在線性時間復雜度 O(n) 內用一趟掃描解決此問題嗎？
• 你能不使用任何內置函數解決此問題嗎？（如，C++ 中的 __builtin_popcount ）

算法思路

遍歷一遍數組，對于每個數，直接使用模板中消去最低位的1，直到變量為零，用一個變量計算次數即可。

代碼實現

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){num&=(num-1);count++;}ans[i] = count;}return ans;}

只出現一次的數字

題目鏈接

136. 只出現一次的數字

題目描述

給你一個 非空 整數數組 nums ，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

你必須設計并實現線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間。

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

示例 2 ：

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

示例 3 ：

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

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某個元素只出現一次以外，其余每個元素均出現兩次。

算法思路

1. 任何數和 0 做異或運算，結果仍然是原來的數，即 a^0=a。
2. 任何數和其自身做異或運算，結果是 0，即 a^a=0。
3. 異或運算滿足交換律和結合律，即 a^b^a=b^a^a=b^(a^a)=b^0=b。

代碼實現

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto num : nums){ret ^= num;}return ret;}
};

只出現一次的數字 II

題目鏈接

137. 只出現一次的數字 II

題目描述

給你一個整數數組 nums ，除某個元素僅出現 一次 外，其余每個元素都恰出現 三次 。請你找出并返回那個只出現了一次的元素。

你必須設計并實現線性時間復雜度的算法且使用常數級空間來解決此問題。

示例 1：

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

示例 2：

輸入：nums = [0,1,0,1,0,1,99]
輸出：99
提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某個元素僅出現 一次 外，其余每個元素都恰出現 三次

算法思路

設要找的數位 ret 。
由于整個數組中，需要找的元素只出現了一次，其余的數都出現的三次，因此我們可以根據所有數的某一個比特位的總和 %3 的結果，快速定位到 ret 的一個比特位上的值是0 還是 1 。
這樣，我們通過 ret 的每一個比特位上的值，就可以將 ret 給還原出來。

代碼實現

class Solution {
public:int singleNumber(vector<int>& nums) {int num = 0;for(int i = 0; i < 32; i++){int count = 0;for(auto n : nums){count += ((n>>i)&1);}if(count % 3)num |= (1<<i);}return num;}
};

只出現一次的數字 III

題目鏈接

260. 只出現一次的數字 III

題目描述

給你一個整數數組 nums，其中恰好有兩個元素只出現一次，其余所有元素均出現兩次。 找出只出現一次的那兩個元素。你可以按 任意順序 返回答案。

你必須設計并實現線性時間復雜度的算法且僅使用常量額外空間來解決此問題。

示例 1：

輸入：nums = [1,2,1,3,2,5]
輸出：[3,5]
解釋：[5, 3] 也是有效的答案。

示例 2：

輸入：nums = [-1,0]
輸出：[-1,0]

示例 3：

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

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
  除兩個只出現一次的整數外，nums 中的其他數字都出現兩次

算法思路

出現兩次的數異或操作后會抵消，而兩個不相等的數異或后的結果，必有一個比特位是為1的，我們根據這個比特位將所有數據分為兩組。即可得出這兩個數。

• 將所有數進行異或操作，異或后的結果中不為零的比特位即為區分點
• 通過找出的區分點，找出兩個數。

代碼實現

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int num = 0;for(auto n : nums){num ^= n;}// 通過最低位的1將數據分為兩組int l = (num==INT_MIN ? num : num&(-num));int sum1 = 0, sum2 = 0;for(auto n : nums){if(n & l)sum1^=n;elsesum2^=n;}return {sum1, sum2};}
};

?? 寫在最后：以上內容是我在學習以后得一些總結和概括，如有錯誤或者需要補充的地方歡迎各位大佬評論或者私信我交流！！！