位运算（一）位运算简单总结

 191. 位1的个数

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中

设置位

的个数（也被称为 汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

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

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

class Solution {
public:int countOnes(int x){int ret = 0;while(x > 0){x &= (x-1);ret++;}return ret;}vector<int> countBits(int n) {vector<int> ans(n+1);for(int i  = 0; i <= n; i++){ans[i] = countOnes(i);}return ans;}
};

减少函数开销 速度由3ms  ->  0ms

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n+1);for(int i = 0; i <= n; i++){int count = 0;int j = i;while(j){j &= (j-1);count++;}ans[i] = count;}return ans;}
};

 461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

• 0 <= x, y <= 231 - 1

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

class Solution {
public:int hammingDistance(int x, int y) {return __builtin_popcount(x ^ y);}
};

136. 只出现一次的数字

 

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

示例 2 ：

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

示例 3 ：

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

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

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]

思路：先整体由小到大排序，从前往后遍历，若i位置元素和下一位置元素相等，则i向后跳俩步，若和下一位置不相等，说明i位置元素即为出现一次的数字。

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());vector<int> res;int i = 0;while(i < nums.size()-1 && res.size() != 2){if(nums[i] != nums[i+1]){res.push_back(nums[i]);i += 1;}elsei += 2;}if(res.size() != 2)res.push_back(nums[nums.size()-1]);return res;}
};

 哈希映射（注意auto 对于哈希表的用法）

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unordered_map<int, int> hash;for(auto e : nums)hash[e]++;vector<int> res;for(const auto & [first, second] : hash)if(second == 1)res.push_back(first);return res;}
};

位运算

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unsigned int temp = 0;for(auto e : nums)temp ^= e;temp = temp & (-temp); // 提取出最右边的1的位置int x1 = 0, x2 = 0;for(auto e : nums){if((e & temp) == 0) // 分为俩组，temp位置为1的进行异或x1 ^= e;else x2 ^= e;cout << x1<<x2; // temp位置不为1的进行异或}return {x1, x2};}
};