题目链接

二进制不同位数

题目描述

给定两个正整数 和 。将它们分别写成二进制串（不含前导零），从最低位对齐后进行比较。请计算在所有对应位上二进制数字不同的位数。这个数值也称为两个数的汉明距离 (Hamming Distance)。

更形式化地，设 表示按位异或 (XOR) 运算，则需要计算的数值等于 的二进制表示中 1 的个数。

输入:

  • 一行两个正整数 和 。

输出:

  • 一个整数，表示 和 的二进制表示中不同的位数。

解题思路

这个问题的核心在于理解按位异或 (XOR) 运算的性质。XOR 运算的规则是：当两个对应的二进制位不同时，结果位为 1；当它们相同时，结果位为 0。

  • 1 ^ 0 = 1
  • 0 ^ 1 = 1
  • 1 ^ 1 = 0
  • 0 ^ 0 = 0

因此，要计算 和 在二进制上有多少位不同，我们只需要计算它们的异或结果 。这个结果中的每一个 1 都精确地对应了 和 在该位上的一个差异。

这样，问题就巧妙地转化为了我们在上一题中解决的问题：计算一个数（即 的结果）的二进制表示中有多少个 1。

解决这个问题的最佳方法是使用编程语言内置的 popcount (population count) 函数，它能高效地统计出 1 的个数。

具体步骤如下：

  1. 计算两个输入整数的按位异或结果：result = m ^ n。
  2. 使用 popcount 函数计算 result 中 1 的数量并输出。

代码

#include <iostream>

using namespace std;

int main() {
    long long m, n;
    cin >> m >> n;
    
    // 1. 计算异或结果
    long long xor_result = m ^ n;
    
    // 2. 使用内置函数计算结果中 1 的个数
    cout << __builtin_popcountll(xor_result) << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long m = sc.nextLong();
        long n = sc.nextLong();
        
        // 1. 计算异或结果
        long xor_result = m ^ n;
        
        // 2. 使用内置函数计算结果中 1 的个数
        System.out.println(Long.bitCount(xor_result));
    }
}

# 读取输入
m, n = map(int, input().split())

# 1. 计算异或结果
xor_result = m ^ n

# 2. 转换为二进制字符串并计算 '1' 的数量
#    这是兼容所有现代 Python 版本的 popcount 实现
print(bin(xor_result).count('1'))

算法及复杂度

  • 算法：位运算 (XOR + Popcount)
  • 时间复杂度： - 按位异或和内置的 popcount 函数通常都对应单条或极少几条CPU指令，其执行时间不随输入数值的大小而改变。
  • 空间复杂度： - 只使用了常数个额外变量。