位运算练习

判断字符是否唯一

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

思路

此题可以用位运算解决，我们这里使用位图。位图：即定义一个数字将其转换为32个二进制位，将其初始化为0，每个字母代表一位，判断每个位置是否为1，如果为0，则将其加一（相当于记录此位置存在一种字母）；如果为1，则之前这种字母已存在，返回false即可。

代码

bool isUnique(string astr)
{if (astr.size() > 26) return false;int bitMap = 0;for (auto ch : astr){int i = ch - 'a';if (((bitMap >> i) & 1) == 1) return false;bitMap |= 1 << i;}return true;
}

丢失的数字

268. 丢失的数字 - 力扣（LeetCode）

思路

我们知道，异或运算的性质是相同返回0，相异返回1，所以我们先创造一个未丢失数字的数组，将其与丢失数字的数组按位异或，相同的值都变成了0，剩余的没有变成0的值即为丢失的数字。

代码

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

两数之和

371. 两整数之和 - 力扣（LeetCode）

思路

按位异或的本质是无进位相加，所以这题我们需要将两数异或并找到进位次数即可。

而按位与的性质是有0则0，所以对于进位，以a,b两数为例，我们选择将两数按位异或的值复制给a，而将两数按位与并向左移1位的值赋值给b（按位与表示两数必须全为1才为1，将得到的值向左移就相当于进位了，而其他的一定至少有一个不为1，因为都为1才进位，所以其他的都变成了0）。

继续循环即可直到没有两位数都为1的情况，即无需进位，最后按位与就会将b变成0，同时，这也是我们循环结束的条件。

代码

int getSum(int a, int b)
{while (b != 0)//算到进位为0为止{int x = a ^ b;unsigned int carry = (unsigned   int)(a & b) << 1;a = x;b = carry;}return a;
}

只出现一次的数字II

137. 只出现一次的数字 II - 力扣（LeetCode）

思路

这题我们将所有数的某一位加起来，因为其他n个数都是相同的，所以有四种情况

3*n + 1 == 3n + 1

3*n == 3n

0 + 1 == 1

0 + 0 == 0

此时我们将得到的值模3，得到的值即为那个只出现一次的数的那一位

代码

int singleNumber(vector<int>& nums)
{int ret = 0;for (int i = 0; i < 32; i++){int sum = 0;for (int x : nums)if (((x >> i) & 1) == 1) sum++;sum %= 3;if (sum == 1) ret |= (1 << i);}return ret;
}

拓展

我们可以总结规律，出现多少次的数我们就将值模多少，这种类型的题目无论元素出现4次还是10次，我们就都可以用这种解法了

消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

思路

我们分步骤解决问题

第一步：与丢失的数字那题类似，我们将缺失数字的数组与原数组按位异或，以a,b为例就可以得到a ^ b的值了。

第二步：找出a和b比特位不同的一位diff，从下标为0开始，相异为1，所以需要找到值为1的那一位

第三步：根据diff将数组划分为两类来异或

代码

vector<int> missingTwo(vector<int>& nums)
{int tmp = 0;for (auto x : nums) tmp ^= x;for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;//找出a和b中比特位不同的一位int diff = 0;while (1){if (((tmp >> diff) & 1) == 1) break;else diff++;}//根据diff位的不同将所有数划分为两类来异或int a = 0, b = 0;for (int x : nums)if (((x >> diff) & 1) == 1) b ^= x;else a ^= x;for (int i = 1; i <= nums.size() + 2; i++)if (((i >> diff) & 1) == 1) b ^= i;else a ^= i;return { a, b };
}

位运算解题技巧

按位与 & :有0则0
按位或 | :有1则1
按位异或 ^: 相同为0，相异为1/不进位相加

1.给一个数n，确定它的二进制表示中的第x位是0还是1
(n >> x) & 1 == 0 -> 0 / 1 -> 1
2.将一个数n的二进制表示的第x位修改成1
n |= (1 << x)
3.将一个数n的二进制表示的第x位修改成0
n &= ~(1 << x)
4.提取一个数(n)二进制表示中最右侧的1
n & (-n)
5.去除一个数(n)二进制表示中最右侧的1
n & (n - 1)
6.异或运算律
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ (b ^ c)(不考虑顺序)