Minimize XOR

This question is also a lot simpler than what it first appears.

Logically, it makes sense that you start to find x by making x = num1 and then continue to add/substract bits. If we denote bits1 and bits2 as the number of set bits in num1 and num2 respectively, then we have 3 potential outcomes:

1. if bits1 < bits2, then we need to add set bits to x. Since we want x to be closest to nums1, we should start adding bits from the least significant bit to minimise the difference.
2. if bits1 = bits2, then just return x as bits1
3. if bits1 > bits2, then we need to remove set bits from x. Since we want x to be closest to nums1, we should start removing bits from the least significant bit to minimise the difference.

Then, we just remove / add bits until the number of set bits in x is equal to the bits in num1s.

code

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int bits1 = __builtin_popcount(num1), bits2 = __builtin_popcount(num2);
        int ans = num1;
        int index = 0;
        while(bits1 != bits2) {
            if (bits1 < bits2 && (1 << index & ans) == 0) {
                ans ^= 1 << index;
                ++bits1;
            } else if (bits1 > bits2 && (1 << index & ans) > 0) {
                ans ^= 1 << index;
                --bits1;
            }
            ++index;
        }
        return ans;
    }
};

complexity

• Time: O(log n)
• Space: O(1)

any learnings:

• __builtin_popcount(num) returns the number of set bits in num