Bit Counter: Finding Single Numbers with XOR Magic

This series covers three problems centered around one core idea: use bitwise operations to build a counter that resets to 0 after counting to K. When we iterate through an array, numbers that appear K times will cancel out to 0 in our counter. The remaining non-zero bits form the number we seek.

Building a Bit Counter

The process has three steps:

1. Count states needed - Figure out how many binary variables represent them For example: 3 states (appearing 3 times) needs 2 bits or 2 variables

2. Build truth table - Get state transition equations Variables include those from step 1 plus each number’s bit (0 or 1). State transitions depend on whether incoming bits are 1 or 0. Use formula manipulation or Karnaugh maps to get transition equations.

3. Code the equations Convert equations to Boolean algebra expressions

Find One Unique Number Among Duplicates

For an array where every number appears twice except one, XOR works beautifully. Since A XOR A = 0 and B XOR 0 = B:

int singleNumber(vector<int>& nums) {
    int res=0;
    for(int i=0;i<nums.size();++i)
        res^=nums[i];
    return res;
}

Find One Unique Number Among Triples

First attempt without simplification:

int singleNumber(vector<int>& nums) {
    int a=0;
    int b=0;
    for(int c : nums) {
        int tmp=(b&c) | ((~c)&a);
        b=(b&(~c)) | ((~a)&(~b)&c);
        a=tmp;
    }

    return b;
}

Simplified version:

int singleNumber(vector<int>& nums) {
    int counterOne = 0;
    int counterTwo = 0;
        
    for (int i = 0; i < nums.size(); i++){
        counterOne = (~counterTwo) & (counterOne ^ nums[i]);
        counterTwo = (~counterOne) & (counterTwo ^ nums[i]);
    }
    return counterOne;
}

Find Two Unique Numbers Among Doubles

This differs from the first problem. XORing all numbers gives us the XOR of two target numbers. We need to separate them. Use the difference mask between the two numbers - this difference is exactly what we get from the first method.

vector<int> singleNumber(vector<int>& nums) {
    int ixorj=0;
    for(int n : nums)
        ixorj^=n;

    // Find a different bit between the two numbers
    int mask=1;
    while((ixorj & mask)==0) mask=mask<<1;

    int i=0;
    int j=0;
    for(int n : nums) {
        // Separate based on the different bit
        if (n & mask)
            i^=n;
        else
            j^=n;
    }

    return vector<int>{i, j};
}

Key Takeaways

1. How to implement and use bit counters
2. The power of XOR operations

#bitwise-operations