文章目录
位运算总结
基础位运算
按位或：| （有1则为1）
按位与：&（有0则为0）
按位异或：^（相同为0相异为1 无进位相加）
如何理解无进位相加，我们看下面这个例子：
确定一个数n的二进制表示中的第X位是0还是1
将一个数n的二进制表示中的第X位修改成1
将一个数n的二进制表示中的第X位修改成0
这道题和上面基本一致，只不过是先把1左移X位后把结果按位取反后再和数n相与：
n &= （~(1 << x)）
提取一个数n二进制表示中最右侧的1(lowbit)
把n按位取反后加1再与1相与： n & -n(在计算机中，复数通常用补码表示）
消除一个数n二进制表示中最右侧的1
n & (n - 1)
n - 1的目的：把最右侧的1右边区域的数(包含1)全部变成相反。
异或运算的运算律
a ^ 0 = a
a ^ a = 0(消消乐)
a ^ b ^ c = a ^ (b ^ c)
也就是说一堆数据相异或结果一定是唯一的，结果和顺序无关。
只出现一次的数字I
题目链接
题目描述
解题思路
这道题用的是异或运算律，把整数数组里的数全部异或在一起，出现偶数次的自然就消为0了，最后出现一次的数和0异或结果就是它本身。
代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int x = 0;
for(int i = 0; i < nums.size(); i++)
{
x ^= nums[i];
}
return x;
}
};
只出现一次的数字III
题目链接
题目描述
解题思路
- 这道题还是用异或运算律来求解，先把所有数据异或到一起，最后结果是两个只出现一次的元素相异或的结果，所以需要执果索因，要通过这个结果找到这两个元素。
思路就是把全部数据分成两部分，每部分分别包含这两个元素的其中一个，这样每一部分就降维成上一题了。- 现在的问题就是找到以什么条件来区分这两部分，这就需要我们抓住异或的特点，两个数据相异或得到的结果的二进制表示中，若其中某一位是1，那么这两个数据的二进制表示中相应的位一定是不同的，一个1，一个0，这样才符合异或规律。
- 有了这个思路，我们不难想到要找结果的二进制表示中的其中一个1，也就是把这个1提取出来，再用这个提取出来的1分别与所有数据相与，结果为0分到同一组，非01分到另外一组。
- 但是这里要特别注意处理结果溢出风险，当结果为INT_MIN时，其二进制表示为100…00（32位），如果把它按位取反再加一就超出的整型最大值了，所以当当结果为INT_MIN时就不用x&(-x)了，因为它本身就只有一位是1，直接用它去和所有数据相与。
代码
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int x = 0;
for(int i = 0; i < nums.size(); i++)
{
x ^= nums[i];
}
//防止溢出
int w = x == INT_MIN ? x : x & (-x);
int m = 0;
int n = 0;
for(auto ch : nums)
{
if(ch & w)
{
m ^= ch;
}
else
{
n ^= ch;
}
}
return {m, n};
}
};
以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~
