# Bit manipulation beats 99.62%

• Find the rightmost set bit, divide numbers into two groups. Each group will end up being one unique number.

``````public int[] singleNumber(int[] nums) {
int result[] = new int[2];
int xor = nums[0];
for (int i=1; i<nums.length; i++)
{
xor ^= nums[i];
}

int bit = xor & ~(xor-1);
int num1 = 0;
int num2 = 0;

for (int num : nums)
{
if ((num & bit) > 0)
{
num1 ^= num;
}
else
{
num2 ^= num;
}
}

result[0] = num1;
result[1] = num2;
return result;
}``````

• How could you come up with this !!!!

• brilliant!!!

• I didn't understand what the following line does. Could you explain it in plain English?

int bit = xor & ~(xor - 1);

• The statement "int bit = xor & ~(xor - 1);" can find the rightmost set bit. For example, for xor = 4, bit = 2, i.e., bit is "00000000000000000000000000000010" in binary format, and the rightmost set bit is the 2nd one from right to left.

• Thanks. One more question: I was wondering what is the rationale behind using the bit variable in the for loop that follows.

• The reason why XOR works is, to separate the 2 unique numbers, their bits will differ in atleast one position, which would be the 1's in XOR. We take the rightmost such 1 from the XOR. This 1 must have come from either numbers, to identify which, we XOR all numbers into 2 sets, one set which had that bit set and one which didn't. In the end, the duplicate numbers will cancel themselves out leaving only the unique numbers in each set.

• This is indeed brilliant! Thanks for sharing that.
So I guess choosing any bit in the XOR would work right? You could just as well choose the leftmost bit.

• Yep, leftmost set bit would yield the same result.

• unimaginable!!

• This post is deleted!

• Fantastic solution.

• brilliant solution

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