title: 2026-01-22-牛客每日一题-二进制不同位数
date: 2026-01-22
tags:
- 算法学习
- 牛客
- 位运算
题目信息
- 平台：牛客
- 题目：二进制不同位数
- 难度：简单
- 题目链接
题目描述
给定两个整数 m、n，计算它们二进制表示中不同位的数量。
初步思路
- 不同位的数量等价于 m 与 n 的异或结果中 1 的个数。
- 用
x = m ^ n得到所有不同位。 - 通过
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;}总结与反思
- 用异或能直接锁定不同位。
- 位计数法比逐位扫描更简洁高效。
