使用位运算如何找到数组中只出现一次的数？

Yuzuriha

发布于 2026-01-14 19:05:39

670

算法解析

位运算是用于二进制的运算符号。而对于多次出现的数字，其二进制都是一模一样的，这里是3次重复的出现是数字。由此我们可以想到，如果我们由低到高去计算为一个bit位上的和，对和取余3。如果为0则代表这个bit位上都是重复出现的数字。如果位1则代表出现的我们要找的数字。我们将这个bit的结果记录，再去计算和判断下一个bit位

代码实现

//计算每一个bit位的和
class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;//ret负责记录每一个bit位的变化情况

        for (int i = 0; i < 32; i++)//一个整型一共有32个bit位
        {
            int sum = 0;
            for (auto& e : nums)
            {

                if (((e >> i) & 1) == 1)//从低到高计算每个元素在同一个bit位上的和
                    sum++;
            }

            sum %= 3;
            if (sum == 1)//当取余结果为1时，说明出现了我们要找的数字，我们将其记录
                ret |= (sum << i);
        }
        return ret;
    }
};