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

【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：

输入： 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

解题方法：位运算

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

若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