Minimize xor

Greedy Bit Manipulation

62.4% acceptance

Feb 25, 2026

1090

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. Return the integer x.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_xor(num1: i32, num2: i32) -> i32 {
    let target_bits = num2.count_ones() as i32;
    let num1_bits = num1.count_ones() as i32;
    let mut x = num1;

    if target_bits < num1_bits {
      // Remove lowest (target_bits - num1_bits) set bits from num1
      let mut to_remove = num1_bits - target_bits;
      let mut bit = 0;
      while to_remove > 0 {
        if (x >> bit) & 1 == 1 {
          x &= !(1 << bit);
          to_remove -= 1;
        }
        bit += 1;
      }
    } else if target_bits > num1_bits {
      // Add lowest unset bits
      let mut to_add = target_bits - num1_bits;
      let mut bit = 0;
      while to_add > 0 {
        if (x >> bit) & 1 == 0 {
          x |= 1 << bit;
          to_add -= 1;
        }
        bit += 1;
      }
    }
    x
  }
}