当前位置：首页 > article >正文

LeetCode3226题. 使两个整数相等的位更改次数（原创）

article 2024/11/7 10:59:58

【题目描述】

给你两个正整数 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

题目链接：. - 力扣（LeetCode）

【解题代码】

package number;

import string.CountAndSay;

public class MinChanges {

    public static void main(String[] args) {
        //int n = 13, k = 4;
        //int n = 21, k = 21;
        int n = 14, k = 13;
        int result = new MinChanges().minChanges(n, k);
        System.out.println("计算结果:" + result);
    }

    public int minChanges(int n, int k) {
        int count = 0;
        int bit1, bit2;
        for (int i = 0; i < Integer.SIZE; i++) {
            bit1 = (n >> i) & 0x01;
            bit2 = (k >> i) & 0x01;
            if (bit1 == 1 && bit2 == 0) count++;
            if (bit1 == 0 && bit2 == 1) return -1;
        }

        return count;
    }
}

【解题思路】

根据题意可以总结出使得n能转变成k的条件是不存在某一bit位，n为0而k为1；另外n转变成k更改次数等于所有的n为1，而k为0的bit位数量之和。算法大致步骤如下，按照整数32位，逐次遍历n和k的第i位比特数值：

如果n和k的第i位比特数值都是0，那么不做任何处理；
如果n的第i位比特数值是1，k的第i位比特数值是0，那么返回的数值加1；
如果n的第i位比特数值是0，k的第i位比特数值是1，那么无法使n等于k，直接返回-1；

根据此思路很快完成代码编写，并提交成功

【解题步骤】

定义三个整形变量，count：更改次数；bit1:n的当前bit位数值（0或1）；bit2:k的当前bit位数值（0或1）
```
int count = 0;
int bit1, bit2;
```

从0到31，依次获取n和k的所有bit位

for (int i = 0; i < Integer.SIZE; i++) {
    bit1 = (n >> i) & 0x01;
    bit2 = (k >> i) & 0x01;

如果bit1数值是1，bit2是0，那么返回的结果count加1；
```
if (bit1 == 1 && bit2 == 0) count++;
```
如果bit1数值是0，bit2是1，那么返回的数值加1，那么无法使n等于k，直接返回-1；
```
if (bit1 == 0 && bit2 == 1) return -1;
```