Igor Perić

Source: https://leetcode.com/problems/minimize-xor/

Problem statement

Given two positive integers num1 and num2, find the integer x such that:

• x has the same number of set bits as num2, and
• The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1‘s in its binary representation.

Example 1:

Input: num1 = 3, num2 = 5
Output: 3
Explanation:
The binary representations of num1 and num2 are 0011 and 0101, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.

Example 2:

Input: num1 = 1, num2 = 12
Output: 3
Explanation:
The binary representations of num1 and num2 are 0001 and 1100, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.

Constraints:

• 1 <= num1, num2 <= 109

Solution

This is a very nice binary arithmetic problem to sharpen the implementation skills.

The intuition is that we want to use as many of the bits as possible to “turn off” the most significant bits of the initial number by coinciding them with the set bits of num1 (since 1 ^ 1 = 0). If there are any remaining bits to place, the approach would be to use them to set the low significant bits by coinciding them with zeroes in num1 (since 1 ^ 0 = 1).

So, we can generate the optimal solution iteratively by performing following steps:

1. Count the number of bits in num2
2. Clear the set bits from the left to the right in num1 (to reduce the resulting number as much as possible towards zero)
3. Place remaining bits in the free positions from the right to the left (to keep the number as small as possible)

Final result is stored in the variable r, which is set to zero at the start and whose bits are set one by one as we’re constructing the solution.

Apparently, C++ implementation bellow resulted in a VERY fast and memory efficient solution:

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int c = 0, r = 0;
        
        // count the set bits in num2
        while (num2) {
            c += (num2 & 1);
            num2 >>= 1;
        }
        
        // clear bits from left to right in num1
        int b = (1 << 30); // start from the right
        while (b) {
            if (b & num1) {
                num1 ^= b; // clear the current bit
                r |= b; // set the bit in the solution
                c--;
                if (c == 0) break;
            }
            b >>= 1; // move the bit to the right
        }
        
        // add the remaining bits from right to left
        b = 1;
        while (c) {
            if (!(r & b)) { // if the current position is free...
                r |= b; // ... set it
                c--;
            }
            b <<= 1;
        }
        
        return r;
    }
};