[LeetCode] 3226. Number of Bit Changes to Make Two Integers Equal

You are given two positive integers n and k.

You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.

Return the number of changes needed to make n equal to k. If it is impossible, return -1.

Example 1:
Input: n = 13, k = 4
Output: 2

Explanation:
Initially, the binary representations of n and k are n = (1101)2 and k = (0100)2.
We can change the first and fourth bits of n. The resulting integer is n = (0100)2 = k.

Example 2:
Input: n = 21, k = 21
Output: 0

Explanation:
n and k are already equal, so no changes are needed.

Example 3:
Input: n = 14, k = 13
Output: -1

Explanation:
It is not possible to make n equal to k.

Constraints:
1 <= n, k <= 106

使两个整数相等的位更改次数。

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

思路

这是一道位运算的问题。首先注意，这道题里我们只能改 n 的某个 digit，不能改 k 中的 digit；而且我们只能把 1 改成 0，不能把 0 改成 1。

那么判断是否能改和怎么改呢？因为不能改 k 中的任何 digit，所以我们可以计算一下 n & k，如果n & k != k，则说明 n 中有一些位置上存在 0，而我们是不能改动 0 的，这种 case 我们就直接返回 -1。如果n & k == k，起码说明我们可以改。此时我们可以用各种语言自带的 API 统计一下 n 和 k 分别包含几个 1，然后返回他们的差值即可。

或者我们也可以看 n | k 是否等于 n，如果等于 n，则说明 k 里面不存在多余的 1。通过这个方式我们也可以判断是否可以改动。

复杂度

时间O(1)
空间O(1)

代码

Java实现

class Solution {
    public int minChanges(int n, int k) {
        return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
    }
}

class Solution {
    public int minChanges(int n, int k) {
        return (n | k) != n ? -1 : Integer.bitCount(n ^ k);
    }
}