神奇的位操作(Bit Manipulation)

位操作无非是与、或、非、异或、移位,原本笔者以为这类题都是白给的,直到遇到leetcode 260,笔者才意识到自己还是太嫩了。

本题给定一个整数数组 nums,其中正好有两个元素只出现一次,所有其他元素只出现两次。我们需要找出只出现一次的两个元素,要求是线性复杂度且仅使用常数额外空间(输入数组不算)的算法。

由于只能使用常数额外空间,简单的 map 遍历是行不通的,笔者又一次陷入冥思苦想甚至在想有没有“少数投票”算法,最后我还是耻辱的点开了题解。

万万没想到是位操作

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long allXor = 0;
        for(auto i : nums)
            allXor ^= i;
        long long rightMostOneBit = allXor & (-allXor);
        int a1 = 0, a2 = 0;
        for(auto i : nums) {
            if(i & rightMostOneBit) a1 ^= i;
            else a2 ^= i;
        }
        
        return vector<int>{a1, a2};
    }
};

理解之后才知道位操作能这么玩儿,首先求出所有元素异或的结果,由于目标元素之外的所有其他元素恰好出现两次,它们异或结果是0,因此allXor结果是目标两个元素的异或结果,其中为1的位是两个数对应位不同的位置。

使用allXor & (-allXor)得到的结果是目标两个元素最右不同的位,根据这一位,我们可以将所有元素按照与最右位 rightMostOneBit 进行与运算是否为1分为两组,目标两个元素肯定在不同组,而且相等的两个元素在同一组,分别求出两个组所有元素的异或结果就是目标元素了。

笔者认为自己关键的两个点没想到,一个是恰好出现两次的元素异或是0,还一个是allXor & (-allXor)获得rightMostOneBit。还是太嫩了呀T_T,今后遇到想不到的位操作还会继续在这篇随笔上更新,吃一堑长一智。

原文地址:https://www.cnblogs.com/lkltcl/p/15389271.html