二进制不同位数

思路

题目很直白：给两个正整数，把它们转成二进制，从最低位对齐，数一下有多少个位置上的数字不一样。

这不就是异或（XOR）吗？异或的性质就是：相同为 0，不同为 1。所以 a ^ b 的结果里有几个 1，答案就是几。

那问题就变成了：怎么数一个数的二进制里有多少个 1？这就是经典的 popcount（population count）问题。

方法有很多：

  • 最简单的：不断 x & (x - 1) 消掉最低位的 1，消了几次答案就是几
  • 偷懒的：直接用语言内置函数。C++ 有 __builtin_popcountll()，Java 有 Long.bitCount()

举个例子：15 ^ 8 = 1111 ^ 1000 = 0111，三个 1，答案就是 3。

代码

#include <iostream>
using namespace std;
int main() {
    long long a, b;
    cin >> a >> b;
    cout << __builtin_popcountll(a ^ b) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        System.out.println(Long.bitCount(a ^ b));
    }
}

a, b = map(int, input().split())
print(bin(a ^ b).count('1'))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [a, b] = line.trim().split(' ').map(BigInt);
    let x = a ^ b;
    let cnt = 0;
    while (x > 0n) {
        cnt += Number(x & 1n);
        x >>= 1n;
    }
    console.log(cnt);
    rl.close();
});

复杂度分析

  • 时间复杂度: ，异或和 popcount 都是常数级别（位数级别）。
  • 空间复杂度: ，只用了几个变量。

小结

这题考的就是对位运算的基本理解。看到「二进制对应位不同」，第一反应就该是异或。异或完数 1 的个数，一行核心代码就搞定了。属于位运算的入门送分题，但很好地帮你建立起「异或 = 找不同」的直觉。