[23333333] really concise C++ implementation


  • 0
    2
    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            int aXorb = 0;
            for(auto item : nums)  aXorb ^= item;
            int lastBit = aXorb & (-aXorb);
            int a = 0, b = 0;
            for(auto item : nums) {
                if(item & lastBit)  a = a ^ item;
                else  b = b ^ item;
            }
            return vector<int>{a, b};
        }
    };
    

    But I am still wondering why the i&(-i) can get the last set bit of i.


  • 0
    J

    -i = (~i) + 1. So, if i is 101010 then ((~i) + 1) is 010110. That means before the last bit 1, i and ((~i) + 1) are different and after the last bit, they are the same.


  • 0
    L

    -i = (~i) + 1 , then (i&(-i)) can get a binary number like(0000...100..0), and the "1" is the last bit 1 in the binary number of i.


Log in to reply
 

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