位运算的两道题目

137 阅读 0 评论 91 点赞

我是靠谱客的博主传统高跟鞋，这篇文章主要介绍位运算的两道题目，现在分享给大家，希望可以做个参考。

做位运算自己一直出错，两道中等的题目代码反而接近两个小时.....

位运算的优先级一直没搞对，有两点需要注意

1.(Xor& count == 0) 会出错，应该写成(Xor & count) == 0

2.curBit << 1; 会出错应该写成curBit = curBit <<1;

面试题56：数组中数字出现的次数

由于符号优先级那里搞错了，(Xor&count) ==0

思路：根据异或结果不为0，然后利用异或结果为1进行切割数组。学习

for(auto it:nums){ if(满足条件) 进桶1

}

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        //  x ^ 0 = x;
        //这个结果就是两个数的Xor节点，我们用它来分组
        int Xor = 0;
        for(auto it : nums){
            Xor ^= it;
        }
        
        //找到1个1即可，用它来进行分组
        int count = 1;
        while( ( Xor & count) == 0){//这里需要小心,((Xor^count))一定要加括号
            count <<= 1;
        }

        //这样的话就得到了count在哪里
        int num1 = 0;
        int num2 = 0;
        for(auto it:nums){
            if( (it & count) == 0){//我他妈服了，这里==号优先级比较大,并且必须是==0/count之前merge也是
                num1 = num1 ^ it;
            }else{
                num2 = num2 ^ it;
            }
        }

        vector<int> res;
        res.push_back(num1);
        res.push_back(num2);
        return res;
    }
};

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/submissions/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //出现了3次的数字，他们那一位相加起来的结果肯定%3=0
        //然后因为
        //[1 2 2 2]
        int res = 0;
        for(int i = 0 ; i < 32 ; i++){
            int curBit = 1 << i; //这种比较巧妙，最多也就是到达了2^31次
            int count = 0 ;
            for(auto it : nums){
                //对于这一位都进行相加
                 if((it & curBit) !=0) count++;
            }
            if((count%3) !=0) res = res | curBit;
            
        }
        return res;
    }
};

过程中也遇到bug，主要说的就是出现了负数左移的情况。

复制代码

1
2
Line 16: Char 28: runtime error: left shift of negative value -2147483648 (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:26:28