题解 | #二进制不同位数#
二进制不同位数
https://www.nowcoder.com/practice/daf9032926614dab91ca624a7759a868
二进制不同位数
思路
题目很直白：给两个正整数，把它们转成二进制，从最低位对齐，数一下有多少个位置上的数字不一样。
这不就是异或（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 的个数，一行核心代码就搞定了。属于位运算的入门送分题，但很好地帮你建立起「异或 = 找不同」的直觉。
查看5道真题和解析
华为HUAWEI公司氛围 747人发布