目标
给你两个正整数 n 和 k。
你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。
示例 1：
输入： n = 13, k = 4
输出： 2
解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，
我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。示例 2：
输入： n = 21, k = 21
输出： 0
解释：
n 和 k 已经相等，因此不需要更改。示例 3：
输入： n = 14, k = 13
输出： -1
解释：
无法使 n 等于 k。说明：
- 1 <= n, k <= 10^6
思路
有两个整数 n 和 k，每次操作可以将 n 的二进制位从 1 改为 0，求使 n 等于 k 所需的操作次数，如果无法实现返回 -1。
注意到这两个整数最大为 10^6，而 2^20 = 1048576，因此最高 bit 位不会超过 20。
依次比较这两个数的第 19 位到第 0 位：
- 如果相等则跳过
- 如果
n的 bit 位为0则返回-1，因为这时k对应位置的 bit 位为1，无法通过操作使之相等 - 否则累加操作次数
官网题解提供了另一种解法，将每个 bit 为 1 的位置视为一个元素，如果可以通过操作将 n 变为 k， 说明 k 的 bit 1 的集合是 n 的 bit 1 集合的子集。因此 n & k = k，这时我们需要统计 n 与 k bit 位不同的个数，直接使用异或运算统计 bit 1 的个数即可。
return (n & k) == k ? Integer.bitCount(n ^ k) : -1;。
代码
/**
* @date 2024-11-02 5:00
*/
public class MinChanges3226 {
public int minChanges(int n, int k) {
int res = 0;
for (int i = 19; i >= 0; i--) {
int bitn = n & 1 << i;
int bitk = k & 1 << i;
if (bitn == bitk) {
continue;
}
if (bitn == 0) {
return -1;
} else {
res++;
}
}
return res;
}
}
性能
