二进制不同位数【牛客tracker 每日一题】
二进制不同位数
时间限制：1秒 空间限制：256M
知识点：位运算
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定两个正整数m mm和n nn。将它们分别写成二进制串（不含前导0 00），从最低位对齐后进行比较。请计算在所有对应位上二进制数字不同的位数，记为f ( m , n ) f(m,n)f(m,n)。
更形式化地，设x = m x=mx=mx o r xorxorn nn，则f ( m , n ) f(m,n)f(m,n)等于x xx的二进制表示中1 11的个数。
输入描述：
在一行上输入两个整数m , n ( 1 ≦ m , n ≦ 10 9 ) m,n(1≦m,n≦10^9)m,n(1≦m,n≦109)，表示需要比较的两个正整数。
输出描述：
在一行上输出一个整数，表示m mm和n nn的二进制表示中不同的位数f ( m , n ) f(m,n)f(m,n)。
示例1
输入：
15 8输出：
3说明：
在这个样例中，m = 15 m=15m=15的二进制为( 1111 ) 2 (1111)_2(1111)2，n = 8 n=8n=8的二进制为( 1000 ) 2 (1000)_2(1000)2。
从最低位对齐后比较四个二进制位，有3 33个位置上的数字不同，因此答案为3 33。
示例2
输入：
7 10输出：
3说明：
在这个样例中，m = 7 m=7m=7的二进制为( 111 ) 2 (111)_2(111)2，n = 10 n=10n=10的二进制为( 1010 ) 2 (1010)_2(1010)2。
补齐后比较四个二进制位：
- 第1 11位（最低位）：1 ≠ 0 1≠01=0；
- 第2 22位：1 = 1 1=11=1；
- 第 3 位：1 ≠ 0 1≠01=0；
- 第 4 位：0 ≠ 1 0≠10=1。
共有3 33个位置不同，故答案为3 33。
解题思路
核心利用异或运算的特性（二进制位相同为0 00、不同为1 11），将问题转化为统计异或结果中1 11的个数；首先读取两个正整数m mm和n nn，计算异或值x = m n x = m ^ nx=mn，x xx的二进制中1 11的位置恰好对应m mm和n nn二进制不同的位；随后采用高效位运算技巧（x & = x − 1 x \& = x-1x&=x−1）统计1 11的个数，该操作每次消去x xx最右侧的1 11，循环执行至x xx为0 00，统计循环次数即为答案；该方法无需补齐二进制位，时间复杂度仅为O ( l o g ( m a x ( m , n ) ) ) O(log(max(m,n)))O(log(max(m,n)))（与两数二进制位数相关），适配m 、 n ≤ 1 e 9 m、n≤1e9m、n≤1e9的规模，避免了逐位遍历的冗余计算，精准且高效地得到两数二进制不同的位数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll m,n;cin>>m>>n;ll x=m^n;ll ans=0;while(x!=0){x&=(x-1);ans++;}cout<<ans<<endl;return0;}