【Leetcode】位运算之只出现一次的数字I、III

---

位运算总结

基础位运算

按位或：| （有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};}
};

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~