题目描述
给你两个正整数 n
和 k
。
你可以选择 n
的 二进制表示 中任意一个值为 1 的位,并将其改为 0。
返回使得 n
等于 k
所需要的更改次数。如果无法实现,返回 -1。
样例
输入: n = 13, k = 4
输出: 2
解释:
最初,n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2,
我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。
输入: n = 21, k = 21
输出: 0
解释:
n 和 k 已经相等,因此不需要更改。
输入: n = 14, k = 13
输出: -1
解释:
无法使 n 等于 k。
限制
1 <= n, k <= 10^6
算法
(位运算) $O(1)$
- 如果 $n$ 按位与 $k$ 的值小于 $k$,则说明存在某一位,满足 $n$ 的值为 $0$,但 $k$ 的值为 $1$,此时返回 -1。
- 否则,求出 $n$ 按位异或 $k$ 的值,这个值的二进制中 1 的个数就是答案。
时间复杂度
- 若干次位运算,时间复杂度为 $O(1)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minChanges(int n, int k) {
if ((n & k) < k)
return -1;
return __builtin_popcount(n ^ k);
}
};