【基础算法总结】位运算

一，常见位运算操作总结

1. 基础位运算符

注意：参与位运算的对象只能是整型数据(int, unsigned, char)，不能为实型。

上面六种基础位运算是本篇文章重点涉及的，要想详细了解它们的含义和运算规律，请点击文章：【移位操作符，位操作符运算规则详解】

2. 位运算符的优先级

只要记住一句话：表格不用死记，能加括号就加括号。

3. 给定一个数 n ，判断他的二进制表示的第 x 位是 0 还是 1？

(n >> x) & 1

4. 将一个数 n 的二进制表示的第 x 位修改成 1

n |= (1 << x)

5. 将一个数 n 的二进制表示的第 x 位修改成 0

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

6. 位图思想

位图的本质是哈希表，是一个用二进制比特位表示数据是否存在的数据结构。

想详细了解什么是位图以及位图的使用，请点击文章：【哈希的应用 – 位图&布隆过滤器】

7. 提取一个数(n)二进制表示中最右侧的 1

n & -n

8. 干掉一个数(n)二进制表示中最右侧的 1

n & (n - 1)

9. 异或(^)运算的运算律

二，算法原理和代码实现

191.位1的个数

算法原理：
根据上面总结的位运算的操作，这道题有两种解法。

代码实现1：

根据上面的第三点，可以判断 n 的二进制里的每一位是否是1，如果是，计数器++。

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

代码实现2：

根据上面的第8点，每次都干掉数 n 的最右侧的1，统计执行的次数即可。

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

338.比特位计数

算法原理：

这道题就是上一题的进阶题，算法原理同上，加一个循环遍历从0到n的数字，分别计算出每个数字的二进制中1的个数，存入数组中即可。

代码实现：

class Solution 
{
public:vector<int> countBits(int n) {vector<int> ret;for(int i = 0; i <= n; i++){int tmp = i;unsigned int count = 0;while(tmp){tmp &= (tmp-1);count++;}ret.push_back(count);}return ret;}
};

461.汉明距离

算法原理：

根据上面的操作三，判断这两个数的每一位是否相等，如果不相等，计数器++ 即可。

代码实现：

class Solution 
{
public:int hammingDistance(int x, int y) {int i = 0;int count = 0;for(; i < 32; i++)if(((x >> i) & 1) != ((y >> i) & 1)) count++;return count;}
};

面试题01.01.判断字符是否唯一

算法原理：
这道题比较简单，有多种解法：一是使用位图思想，二是使用哈希表，三是用数组模拟哈希。

这里介绍位图思想。

用一个 int 变量的32个比特位(实际上只使用26个)来标记这个字符在或不在，0 表示不在，1 表示在。
所以先要判断二进制中的第 n 位是 1 还是 0，如果是 0，就修改成 1，如果已经是 1 了，说明这个字符就已经存在了，返回false。

这里还有一个小的优化点：

由鸽巢原理(抽屉原理)可知，当字符串的长度大于26个时，一定会出现重复字符。

代码实现1：使用位图思想

class Solution
{
public:bool isUnique(string astr){if(astr.size() > 26) return false;int bitMap = 0;for (auto ch : astr){int i = ch - 'a'; // 移动的位数// 字符不存在，映射位置的比特位修改成1if (((bitMap >> i) & 1) == 0) bitMap |= (1 << i);else return false;}return true;}
};

代码实现2：使用哈希表
时间复杂度：O(N)
空间复杂度：O(N)

class Solution
{
public:bool isUnique(string astr){if(astr.size() > 26) return false;unordered_map<char, int> hash;for (auto ch : astr){// 判断是否存在if (hash.count(ch) == 0) hash[ch]++;else return false;}return true;}
};

代码实现3：用数组模拟哈希

class Solution
{
public:bool isUnique(string astr){if(astr.size() > 26) return false;int hash[26] = { 0 };for (auto ch : astr){if (hash[ch - 'a'] == 0) hash[ch - 'a']++;else return false;}return true;}
};

268.丢失的数字

算法原理：
这道题其实和 [二分查找] 系列中的最后一题是一模一样的，题目简单，解法多种。

这里介绍使用位运算。

使用异或运算的规律：
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ (b ^ c)
可以先把完整的 [0, n] 共 n + 1 个数进行异或，再把这个异或结果异或上题目所给的数据，相同数异或变成0，最后剩下的那个就是缺失的数字。

代码实现：

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i <= nums.size(); i++)ret ^= i;for(auto x : nums)ret ^= x;return ret;}
};

如果想要了解其他解法，请点击文章：【二分查找】里的最后一题 [LCR173.点名]。

371.两整数之和

算法原理：

这道题使用异或运算 – 无进位相加。
先算出无进位相加的结果，再算出进位，再把两者相加，但是不能使用加法，要重复执行上面两个操作，直到进位为 0 为止。

代码实现：

class Solution 
{
public:int getSum(int a, int b) {int tmp = a ^ b; // 无进位相加的结果int res = (a & b) << 1; // 算出进位// 当进位不为0时，重复上面操作while(res){a = tmp;b = res;tmp = a ^ b;res = (a & b) << 1;}return tmp;}
};

136.只出现一次的数字

算法原理：

这道题很简单，就是对异或运算律(a ^ a = 0)的简单使用。

代码实现：

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

137.只出现一次的数字II

算法原理：

把所有数据的第 i 个二进制位相加，和会出现下面4种情况：

用相加的和取模3(%3)，如果是三个相同的数，它们的第 i 个二进制位相加结果模3为 0，如果等于 1，说明这个二进制位是那个只出现一次的数的，就把它映射到另一个 int 变量的对应的二进制位上。

代码实现：

class Solution 
{
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int sum = 0;for(auto x : nums)sum += ((x >> i) & 1); // 把所有数字的第i个二进制位相加// 如果等于1，说明是出现一次的，把1映射到相应的二进制位if(sum % 3 != 0) ret |= (1 << i);  }return ret;}
};

260.只出现一次的数据III

算法原理：

其实根据 [136.只出现一次的数字] 对这道题是有思路的，就是相同的数异或在一起就变成0了，关键就是如何把相同的数放到一组？

代码实现：

class Solution 
{
public:vector<int> singleNumber(vector<int>& nums) {int tmp = 0;// 把所有数据异或在一起for(auto x : nums)tmp ^= x;// 找出tmp中，比特位上为1的位置int i = 0;for(; i < 32; i++)if((tmp >> i) & 1) break;// 根据i的位置把数据分成两类,分别异或int a = 0, b = 0;for(auto x : nums)if((x >> i) & 1) a ^= x;else b ^= x;return {a, b};}
};

面试题17.19.消失的两个数字

算法原理：
这道题本质上是 [268.消失的数字] 和 [260.只出现一次的数字III] 的结合题。

代码实现：

class Solution 
{
public:vector<int> missingTwo(vector<int>& nums) {int tmp = 0;// 把所属异或在一起for(auto x : nums) tmp ^= x;for(int k = 1; k <= nums.size()+2; k++) tmp ^= k;// 找到tmp中，比特位上为1的那一位int i = 0;for(; i < 32; i++)if((tmp >> i) & 1) break;// 根据第i位的不同，把所有数据分成两类int a = 0, b = 0;for(auto x : nums)if((x >> i) & 1) a ^= x;else b ^= x;for(int j = 1 ; j <= nums.size()+2; j++)if((j >> i) & 1) a ^= j;else b ^= j;return {a, b};}
};

三，算法总结

熟练使用位运算的操作即可。