2429

2429. Minimize XOR (Medium)

Given two positive integers num1 and num2, find the positive 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

Companies: Adobe

Related Topics:
Greedy, Bit Manipulation

Similar Questions:

• Maximum XOR of Two Numbers in an Array (Medium)
• Maximum XOR With an Element From Array (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/minimize-xor
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int minimizeXor(int a, int b) {
        int ca = __builtin_popcount(a), cb = __builtin_popcount(b);
        if (ca == cb) return a;
        if (ca < cb) { // start from a, add missing 1s from the right
            int ans = a;
            cb -= ca;
            for (int i = 0; i < 32 && cb; ++i) {
                if (ans >> i & 1) continue;
                ans |= 1 << i;
                --cb;
            }
            return ans;
        }
        // start from 0, add 1s from the right of a
        int ans = 0;
        for (int i = 31; i >= 0 && cb; --i) {
            if (a >> i & 1) {
                ans |= 1 << i;
                --cb;
            }
        }
        return ans;
    }
};