LeetCode 3226.使两个整数相等的位更改次数：位运算（接近O(1)的做法）

【LetMeFly】3226.使两个整数相等的位更改次数：位运算（接近O(1)的做法）

力扣题目链接：https://leetcode.cn/problems/number-of-bit-changes-to-make-two-integers-equal/

给你两个正整数 n 和 k。

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

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

 

示例 1：

输出： 2

解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，

我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。

示例 2：

输出： 0

解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输出： -1

解释：
无法使 n 等于 k。

 

提示：

• 1 <= n, k <= 106

解题方法：位运算

如何通过位运算判断能否实现？

若n | k == n则说明n二进制下为0的位在k中也都为0，说明可行。

可行情况下如何快速统计需要修改多少次？

n 异或 k后，二者二进制不同的位将会变成1，相同的位则会变成0。因此使用内置函数统计n 异或 k的结果中有多少个1即为答案。

• 时间复杂度$O(1)$。统计二进制下有多少个1的时间复杂度可能和编程语言以及CPU有无对应指令有关，可以是$O(1)$或近似看成$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

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

C++（非位运算但纯模拟版本）

$O(\log \max n)$

class Solution {
public:int minChanges(int n, int k) {int ans = 0;for (int i = 0; i < 20; i++) {int thisN = n & (1 << i), thisK = k & (1 << i);if (thisN && !thisK) {ans++;} else if (thisN != thisK) {return -1;}}return ans;}
};

Python

class Solution:def minChanges(self, n: int, k: int) -> int:return (n ^ k).bit_count() if (n | k) == n else -1

Java

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

Go

package main
import "math/bits"func minChanges(n int, k int) int {if n | k == n {return bits.OnesCount(uint(n ^ k))}return -1
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143448117