题目信息

  • 平台：牛客
  • 题目：二进制不同位数
  • 难度：简单
  • 题目链接

题目描述

给定两个整数 m、n，计算它们二进制表示中不同位的数量。

初步思路

  1. 不同位的数量等价于 m 与 n 的异或结果中 1 的个数。
  2. 用 x = m ^ n 得到所有不同位。
  3. 通过 x &= x - 1 每次消去最低位的 1，并计数。
示例
x     = 1100111 | 1100100
x-1   = 1100110 | 1100011
x&x-1 = 1100110 | 1100000

最低位的1消去了

算法分析

  • 核心：异或 + 统计二进制 1 的个数
  • 技巧：Brian Kernighan 位计数法
  • 时间复杂度：O(k)，k 为不同位数量（x 中 1 的个数）
  • 空间复杂度：O(1)

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    int x = m ^ n;
    int ans = 0;
    while (x != 0) {
        x &= x - 1;
        ++ans;
    }
    cout << ans;
    return 0;
}

总结与反思

  1. 用异或能直接锁定不同位。
  2. 位计数法比逐位扫描更简洁高效。