C++ Solution with comments which doesn't iterate over pairs of bits but uses 2 words as the accumulator


  • 0
    D
    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            typedef int int_t;
            // x1: All bits that occurred 1 times (i.e. xor of all the numbers).
            // x2: All bits that occurred 2 times (should be empty at the end of the cycle).
            int_t x1 = 0, x2 = 0;
            for (int_t num: nums) {
                int_t xp1 = x1;
                x1 ^= num;
                int_t xdiff1 = xp1 & (~x1); // all bits that went from 1 to 0 in x1.
                x2 ^= xdiff1;
                int_t x3 = x1 & x2; // All bits that appeared 3 times so far.
                x1 &= ~x3; // Unset them in x1.
                x2 &= ~x3; // Unset them in x2.
            }
            return x1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.