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

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

article 2025/3/13 1:13:56

二进制位更改：计算将 `n` 变为 `k` 的最少操作次数

问题引入

在编程的世界里，二进制操作是一个既基础又充满挑战的领域。今天我们来探讨一个有趣的问题：给定两个正整数 n 和 k，你可以选择 n 的二进制表示中任意一个值为 1 的位，并将其改为 0，要求返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

问题分析

可行性判断

首先，我们要思考在什么情况下可以将 n 通过把某些 1 位变为 0 位来得到 k。如果 k 的二进制表示中存在 n 对应位置为 0 的 1，那么无论怎么操作 n，都不可能将其变为 k。因为我们只能把 n 中的 1 变为 0，而不能将 0 变为 1。

更改次数计算

当确定可以将 n 变为 k 后，我们需要计算具体的更改次数。实际上，这个次数就是 n 的二进制表示中那些在 k 对应位置为 0 的 1 的数量。

代码实现

#include <stdio.h>

// 计算将 n 变为 k 所需的最少更改次数
int minChanges(int n, int k) {
    // 检查 k 中是否存在 n 对应位置为 0 的 1
    if ((n | k) != n) {
        return -1;
    }

    // 统计 n 中需要更改的位的数量
    int diff = n ^ k;
    int count = 0;
    while (diff) {
        count += diff & 1;
        diff >>= 1;
    }

    return count;
}

int main() {
    int n, k;
    // 提示用户输入两个正整数 n 和 k
    printf("请输入两个正整数 n 和 k，用空格分隔：");
    // 读取用户输入的两个整数
    if (scanf("%d %d", &n, &k) != 2) {
        printf("输入无效，请输入两个有效的整数。\n");
        return 1;
    }

    // 调用 minChanges 函数计算结果
    int result = minChanges(n, k);
    // 输出计算结果
    printf("将 %d 变为 %d 所需的最少更改次数为：%d\n", n, k, result);

    return 0;
}

代码解释

可行性检查：
- 使用按位或运算符 | 来判断 k 中是否存在 n 对应位置为 0 的 1。如果 (n | k) != n，说明 k 中有 n 对应位置为 0 的 1，此时无法将 n 变为 k，返回 -1。
计算需要更改的位的数量：
- 使用按位异或运算符 ^ 计算 n 和 k 的差异 diff。异或操作的特点是相同位为 0，不同位为 1，所以 diff 中为 1 的位就是 n 和 k 不同的位。
- 通过循环，使用按位与运算符 & 检查 diff 的最低位是否为 1，如果是则 count 加 1，然后将 diff 右移一位，继续检查下一位，直到 diff 变为 0。
main 函数：
- 提示用户输入两个正整数 n 和 k。
- 使用 scanf 函数读取用户输入的两个整数，并检查输入是否有效。
- 调用 minChanges 函数计算结果。
- 输出计算结果。