Question

2429. 最小异或

English Version

题目描述

给你两个正整数 num1 和 num2 ，找出满足下述条件的正整数 x ：

• x 的置位数和 num2 相同，且
• x XOR num1 的值 最小

注意 XOR 是按位异或运算。

返回整数_ _x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。

整数的 置位数 是其二进制表示中 1 的数目。

 

示例 1：

输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同，且 3 XOR 3 = 0 是最小的。

示例 2：

输入：num1 = 1, num2 = 12
输出：3
解释：
num1 和 num2 的二进制表示分别是 0001 和 1100 。
整数 3 的置位数与 num2 相同，且 3 XOR 1 = 2 是最小的。

 

提示：

• 1 <= num1, num2 <= 109

解法

方法一：贪心 + 位运算

根据题目描述，我们先求出 $num2$ 的置位数 $cnt$，然后从高位到低位枚举 $num1$ 的每一位，如果该位为 $1$，则将 $x$ 的对应位设为 $1$，并将 $cnt$ 减 $1$，直到 $cnt$ 为 $0$。如果此时 $cnt$ 仍不为 $0$，则从低位开始将 $num1$ 的每一位为 $0$ 的位置设为 $1$，并将 $cnt$ 减 $1$，直到 $cnt$ 为 $0$。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为 $num1$ 和 $num2$ 的最大值。

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

class Solution {
  public int minimizeXor(int num1, int num2) {
    int cnt = Integer.bitCount(num2);
    int x = 0;
    for (int i = 30; i >= 0 && cnt > 0; --i) {
      if ((num1 >> i & 1) == 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    for (int i = 0; cnt > 0; ++i) {
      if ((num1 >> i & 1) == 0) {
        x |= 1 << i;
        --cnt;
      }
    }
    return x;
  }
}

class Solution {
public:
  int minimizeXor(int num1, int num2) {
    int cnt = __builtin_popcount(num2);
    int x = 0;
    for (int i = 30; ~i && cnt; --i) {
      if (num1 >> i & 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    for (int i = 0; cnt; ++i) {
      if (num1 >> i & 1 ^ 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    return x;
  }
};

func minimizeXor(num1 int, num2 int) int {
  cnt := bits.OnesCount(uint(num2))
  x := 0
  for i := 30; i >= 0 && cnt > 0; i-- {
    if num1>>i&1 == 1 {
      x |= 1 << i
      cnt--
    }
  }
  for i := 0; cnt > 0; i++ {
    if num1>>i&1 == 0 {
      x |= 1 << i
      cnt--
    }
  }
  return x
}

function minimizeXor(num1: number, num2: number): number {
  let cnt = 0;
  while (num2) {
    num2 &= num2 - 1;
    ++cnt;
  }
  let x = 0;
  for (let i = 30; i >= 0 && cnt > 0; --i) {
    if ((num1 >> i) & 1) {
      x |= 1 << i;
      --cnt;
    }
  }
  for (let i = 0; cnt > 0; ++i) {
    if (!((num1 >> i) & 1)) {
      x |= 1 << i;
      --cnt;
    }
  }
  return x;
}

方法二

class Solution:
  def minimizeXor(self, num1: int, num2: int) -> int:
    cnt1 = num1.bit_count()
    cnt2 = num2.bit_count()
    while cnt1 > cnt2:
      num1 &= num1 - 1
      cnt1 -= 1
    while cnt1 < cnt2:
      num1 |= num1 + 1
      cnt1 += 1
    return num1

class Solution {
  public int minimizeXor(int num1, int num2) {
    int cnt1 = Integer.bitCount(num1);
    int cnt2 = Integer.bitCount(num2);
    for (; cnt1 > cnt2; --cnt1) {
      num1 &= (num1 - 1);
    }
    for (; cnt1 < cnt2; ++cnt1) {
      num1 |= (num1 + 1);
    }
    return num1;
  }
}

class Solution {
public:
  int minimizeXor(int num1, int num2) {
    int cnt1 = __builtin_popcount(num1);
    int cnt2 = __builtin_popcount(num2);
    for (; cnt1 > cnt2; --cnt1) {
      num1 &= (num1 - 1);
    }
    for (; cnt1 < cnt2; ++cnt1) {
      num1 |= (num1 + 1);
    }
    return num1;
  }
};

func minimizeXor(num1 int, num2 int) int {
  cnt1 := bits.OnesCount(uint(num1))
  cnt2 := bits.OnesCount(uint(num2))
  for ; cnt1 > cnt2; cnt1-- {
    num1 &= (num1 - 1)
  }
  for ; cnt1 < cnt2; cnt1++ {
    num1 |= (num1 + 1)
  }
  return num1
}

function minimizeXor(num1: number, num2: number): number {
  let cnt1 = bitCount(num1);
  let cnt2 = bitCount(num2);
  for (; cnt1 > cnt2; --cnt1) {
    num1 &= num1 - 1;
  }
  for (; cnt1 < cnt2; ++cnt1) {
    num1 |= num1 + 1;
  }
  return num1;
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}