Minimize XOR — LeetCode 2429 Python Solution

The problem

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.

Example

Input

num1 = 3, num2 = 5

Output

3

Explanation

The binary representations of num1 and num2 are 0011 and 0101, respectively.

Python solution

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        cnt = num2.bit_count()
        x = 0
        for i in range(30, -1, -1):
            if num1 >> i & 1 and cnt:
                x |= 1 << i
                cnt -= 1
        for i in range(30):
            if num1 >> i & 1 ^ 1 and cnt:
                x |= 1 << i
                cnt -= 1
        return x

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2429. Minimize XOR is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems