博客网_网络信息化建设方案_友情链接检测方法_百度官方人工客服电话

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

示例 1：

输入： n = 13, k = 4

输出： 2

解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，

我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。

示例 2：

输入： n = 21, k = 21

输出： 0

解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13

输出： -1

解释：
无法使 n 等于 k。

提示：

• 1 <= n, k <= 10e6

分析：模拟。将n和k转化为2进制表示，再进行比较。

int minChanges(int n, int k) {int cnt=0;int num[22]={1},num_n[22]={0},num_k[22]={0};for(int i=1;i<=20;++i)num[i]=num[i-1]*2;for(int i=20;i>=0;--i){if(n>=num[i])num_n[i]=1,n-=num[i];if(k>=num[i])num_k[i]=1,k-=num[i];if(num_n[i]==1&&num_k[i]==0)cnt++;else if(num_n[i]==0&&num_k[i]==1)return -1;}return cnt;
}

当然官方题解的两种更加快速。

第一种是模拟。从低位到高位枚举 n 和 k 的二进制位。

第二种是位运算。若n&k!=k，说明不能实现，否则统计n^k中位为1的个数。