2026-01-22-牛客每日一题-二进制不同位数

title: 2026-01-22-牛客每日一题-二进制不同位数
date: 2026-01-22
tags:

• 算法学习
• 牛客
• 位运算

题目信息

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

题目描述

给定两个整数 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++）

/* * @Author: tkzzzzzz6 * @Date: 2026-01-22 22:21:35 * @LastEditors: tkzzzzzz6 * @LastEditTime: 2026-01-22 22:21:39 */#include<iostream>usingnamespacestd;intmain(){intm,n;cin>>m>>n;intx=m^n;intans=0;while(x!=0){x&=x-1;++ans;}cout<<ans;return0;}

总结与反思

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