跳转至

算法笔记

BISHI31 二进制不同位数

w3903771/algorithm

BISHI31　二进制不同位数¶

简单通过率 60.1%python3样例通过牛客 AC位运算

牛客原题　源码

讲解章节：数据类型与转换、运算符与位运算、位运算

一句话

求 m 与 n 二进制对应位不同的位数。

解题思路¶

这题考什么¶

异或的定义就是「相同为 0，不同为 1」，所以 m xor n 的二进制里每个 1 恰好标记了一个「两数不同」的位，答案 = popcount(m xor n) （popcount 即位计数，统计二进制表示中 1 的个数）。题面自己也把这条公式写了出来，核心只有一行。

这类「逐位比较」的需求几乎都能归约成一次位运算再数 1，不必真的把两个数展开成字符串对齐比较。位运算的系统讲解见 46-位运算。

数据规模与复杂度¶

m,n <= 1e9 < 2^30，单组数据，O(30)。

坑在哪¶

「从最低位对齐」意味着高位缺失的那一方补 0，异或天然就是这个语义，不用手动补齐字符串（手动补齐还容易把前导零算进去）；
Python 3.9 没有 int.bit_count()，用 bin(...).count('1')；
位数不同的两个数（如 7 与 10）高位补 0 后仍要比较，样例 2 就是在考这个，异或写法自动覆盖。

参考实现¶

solutions/BISHI31.py
import sys

# 一行两个数，整块读入后取前两个 token
m, n = map(int, sys.stdin.buffer.read().split()[:2])
# 异或把「对应位不同」变成 1，再数 1 的个数；高位缺失的一方按 0 参与运算
print(bin(m ^ n).count("1"))