题目链接

二进制不同位数

题目描述

给定两个正整数 和 。将它们分别写成二进制串（不含前导 0），从最低位对齐后进行比较。请计算在所有对应位上二进制数字不同的位数，记为 。

更形式化地，设 表示 和 的按位异或（XOR），则 等于 的二进制表示中 1 的个数。

解题思路

这个问题要求我们计算两个整数 和 在二进制表示下有多少位是不同的。这在信息论中被称为“汉明距离”（Hamming distance）。

我们可以利用按位异或（XOR, 在C++/Java/Python中用 ^ 表示）运算的性质来解决这个问题。XOR 运算的规则是：

观察可以发现，只有当两个比较的位不同时，XOR 的结果才为 1；如果两个位相同，结果则为 0。因此，计算 的结果，其二进制表示中 '1' 的个数就恰好是 和 二进制表示中不同位的数量。

所以，问题被成功地转化为了：计算单个整数 的二进制表示中有多少个 1。

这个问题被称为“位计数”（population count 或 popcount）。大多数编程语言都提供了高效的内置函数来完成这个任务：

  • C++: 可以使用 __builtin_popcount(x) (对于 int) 或 __builtin_popcountll(x) (对于 long long)。这些是 GCC 和 Clang 的扩展，但在竞赛环境中被广泛支持。C++20 标准引入了 std::popcount。
  • Java: 可以使用 Integer.bitCount(x) 或 Long.bitCount(x)。
  • Python: 可以使用 bin(x).count('1')，它将数字转换为二进制字符串然后统计 '1' 的数量。

通过这个方法，我们可以非常简洁地解决问题。

代码

#include <iostream>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    // C++ 中 __builtin_popcount 可以直接计算一个整数的二进制表示中1的个数
    cout << __builtin_popcount(m ^ n) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        // Java 中 Integer.bitCount 可以直接计算一个整数的二进制表示中1的个数
        System.out.println(Integer.bitCount(m ^ n));
    }
}

# 读入两个整数
m, n = map(int, input().split())
# Python 中可以通过 bin() 函数转为二进制字符串，再用 count() 方法统计'1'的个数
print(bin(m ^ n).count('1'))

算法及复杂度

  • 算法：位运算
  • 时间复杂度：。计算异或和统计二进制中 1 的个数的操作，其时间复杂度与操作数的二进制位数成正比。对于内置函数，其实现通常是硬件级别的，效率极高，也可以近似看作 。
  • 空间复杂度：，只使用了常数个变量。