class Solution {
public:
int minChanges(int n, int k) {
}
};
100372. 使两个整数相等的位更改次数
给你两个正整数 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 <= 106原站题解
javascript 解法, 执行用时: 1 ms, 内存消耗: 50.9 MB, 提交时间: 2024-11-02 00:57:39
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var minChanges = function(n, k) {
return k & ~n ? -1 : bitCount32(n ^ k);
};
function bitCount32(n) {
n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
javascript 解法, 执行用时: 0 ms, 内存消耗: 50.9 MB, 提交时间: 2024-11-02 00:57:07
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var minChanges = function(n, k) {
return (n & k) !== k ? -1 : bitCount32(n ^ k);
};
function bitCount32(n) {
n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-07-22 22:52:55
func minChanges(n, k int) int {
if n&k != k {
return -1
}
return bits.OnesCount(uint(n ^ k))
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.9 MB, 提交时间: 2024-07-22 22:52:43
class Solution {
public int minChanges(int n, int k) {
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.8 MB, 提交时间: 2024-07-22 22:52:31
class Solution {
public:
int minChanges(int n, int k) {
return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
}
};
python3 解法, 执行用时: 37 ms, 内存消耗: 16.4 MB, 提交时间: 2024-07-22 22:52:18
'''
从集合的角度理解，k 必须是 n 的子集。如果不是，返回 −1。怎么用位运算判断，见上面的文章链接。
如果 k 是 n 的子集，答案为从 n 中去掉 k 后的集合大小，即 n⊕k 的二进制中的 1 的个数。
'''
class Solution:
def minChanges(self, n: int, k: int) -> int:
return -1 if (n & k) != k else (n ^ k).bit_count()