Parsing of bits with XOR and Complement

Question

I have a problem to locate the number which occurs only once when all other numbers in the vector occur exactly thrice.

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        int ones = 0;
        int twos = 0;

        for(const int& n : nums)
        {
            ones = (ones ^ n) & ~twos;
            twos = (twos ^ n) & ~ones;


            std::cout << ones << "\t" << twos << "\n";
        }

        return ones;
    }
};

For an input 2,2,5,5,9,2,5 The ones and twos take these values in various passes

Ones Twos
2     0
0     2
5     2
0     7
8     6
8     4
9     0

My question is How do i know that the algorithm would have worked as the XOR and Complement are yielding values like 0 7 , 8 4 and 8 6 in between the passes which are not even in the integer values being parsed.

I don't understand what's the theorem here which ensures that all these intermediate values will end up as being reduced to value which occurs only one in the input vector. How am i be fully sure that yes all these intermediate results will get cleared and end up being the value which i want to detect.

Can anyone explain ?

I just understand that ones = (ones ^ n) & ~twos; means that add to ones if it doesn't exist in twos and twos = (twos ^ n) & ~ones; means that add to twos if it doesn't exist already in ones. That's all i understand. I don't understand the logic behind the intermediate unrelated values making way to value which is the result.

Answer 1

The calculations are confusing in that ones is updated using the existing value of twos but twos is updated using the updated value of ones in each iteration.

Try drawing a trace table like this (The former 3 columns are in decimal and the latter 6 are binary):

existing ones	existing twos	n	n ^ ones	n ^ twos	~existing twos	new ones	~new ones	new twos
0	0	2	0010	0010	1111	0010	1101	0000
2	0	2	0000	0010	1111	0000	1111	0010
0	2	5	0101	0111	1101	0101	1010	0010
5	2	5	0000	0111	1110	0000	1111	0111
0	7	9	1001	1110	1000	1000	0111	0110
8	6	2	1010	0100	1001	1000	0111	0100
8	4	5	1101	0001	1011	1001	0110	0000

To calculate the new value for the 7th column, do a bitwise AND on the 4th and 6th columns. To calculate the new value for the 9th column, do a bitwise AND on the 5th and 8th columns. Carry the binary values from the 7th and 9th columns to the new row.

You could also create temporary variables for each of these columns and include their values in your debug output.