位运算应用.md

位运算

位运算性质

任意一个数x，

• x^1=~x，x^0=x
• x&1通常用于计算x最后一位是否是1
• x|0通常用于计算x最后一位知否为0

题目 LeetCode136. 只出现一次的数字 I。除了一个数字出现一次，其他都出现了两次，让我们找到出现一次的数。

分析：全员异或就可以。

题目 LeetCode137. 只出现一次的数字 II。除了一个数字出现一次，其他都出现了三次，让我们找到出现一次的数。

分析：统计每一位1出现的次数，如果这一位出现的次数不是三的倍数，那么只出现1次的那个数该位是1。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        //用一个数表示，节省空间
        for(int i = 0; i < 32; i++){
            int count = 0;
            for(int num: nums){
                int temp = num>>i;
                if((temp&1)==1){//判断这一位是否为1
                    count++;
                }
            }
            if((count%3) != 0){
                int temp = 1<<i;
                ans = ans| temp;
            }
        }
        return ans;
    }
};

总结 如果数组中要找的那个数只出现一次的题，如果其他数字出现偶数次，那么全员异或。如果其他数字出现奇数次，那么统计每一位1出现的次数。

题目 LeetCode面试题56. 数组中数字出现的次数。一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：因为数组其他元素出现两次，对所有元素进行异或，那么结果即是要找的两个数字的异或的结果。在结果中随便找一个地方为1的位置（结果中必定至少有一位为1），说明在该位置要找的两个数字不同（因为异或结果为1）。然后根据该位置是否为1，将数组分为两块，分别进行异或，两边的结果就是要找的值。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xorRes = 0;
        //异或所有的数
        for(int num : nums){
            xorRes = xorRes ^ num;
        }
        int bit = 0;
        while((xorRes & 1) == 0){
            bit++;
            xorRes = xorRes >> 1;
        }
        int left = 0, right = 0;
        for(int num:nums){
            int tmp = num>>bit;
            if((tmp&1) == 0){
                left = left^num;
            }else{
                right = right^num;
            }
        }
        vector<int> ans;
        ans.push_back(left);
        ans.push_back(right);
        return ans;
    }
};