前言
一道感觉不难，但是涉及到负数移位运算的坑的题。
正文
题目
如果要将整数A转换为B，需要改变多少个bit位？
（两个数都是32位的整数）
样例
如把31转换为14，需要改变2个bit位。
(31)10=(11111)2
(14)10=(01110)2
思路：
恩，就是找对应位上不同的个数，所以想法就是统计两个数异或后的结果中1的个数，（有1就说明对应位上两个数不相同）。
int bitSwapRequired(int a, int b) {
int result = 0;
int temp = a ^ b;
while(temp){
result += 0x01 & temp;
temp = temp >> 1;
}
return result;
}直接超时，卡在-1,1 这组用例上了。
emmmmm还有负数啊。
超时的原因
我们知道，负数是按照补码的形式进行存储和运算的，以char类型为例（懒得打32位） 1就是0000 0001，而-1则是1111 1111.
在C/C++中的移位运算对于正数是定义的,而对于负数则是依赖于实现的[1][2] (妈蛋C/C++就是好多undefined).
不过大多数实现表现出的行为是一样的.以我们上面定义的1和-1为例
char a = 1,b = -1;
char left_shift_a = a << 1;
char right_shift_a = a >> 1;
char left_shift_b = b << 1;
char right_shift_b = b >> 1;
printf("%d,%d,%d,%d,",left_shift_a,right_shift_a,left_shift_b,right_shift_b);如果你的结果是
2,0,-2,-1恭喜你,可以继续往下看了(毕竟是依赖编译器实现的东西).
对于正数,左移最低位补0,右移最高位补0.
对于负数,以-1来说.
1111 1111 左移一位是 1111 1110(最低位补0) 取反+1之后是 1000 0010,变成-2了.
1111 1111 右移一位是 1111 1111 什么??没有变化? 这是因为对于最高位符号位编译器按照之前的符号位 置1了,所以一个负数右移之后还是负数(标志位始终为1),所以依然是-1. (恩,可以思考一下-2右移一位是?)
OK,知道这些之后,超时的原因就找到了
int temp = a ^ b;
//当ab中有一个为负数时,temp也是负数(或者说标志位为1)
while(temp){
// ....
temp = temp >> 1; //无论怎么右移,负数依然是负数,不可能为0,死循环了.
}再次尝试
enmmm卡在负数了,于是我想着,将负数的标志位置0(其他位不变),然后再进行异或
int result = 0;
if(a * b < 0){ //
a &= 0x7fffffff;
b &= 0x7fffffff;
result++; //标志位肯定不同 所以result++
}
// ...恩,并不成功,这次卡在-1 -2147483648这组边界值上了…
-2147483648就是int类型的下界,就相当于char的-128(你能写出-128的补码吗? 是1000 0000)
这两个数相乘的结果是小于0的…(呃,溢出了),所以GG了.
于是跑去看正解了QAQ
正解
//程序来自九章算术
int count = 0;
for (unsigned int c = a ^ b; c != 0; c = c >> 1) {
count += c & 1;
}
return count;我去,和我第一次的没啥区别…
关键在于人家使用了unsigned int而我是int
这样异或之后的结果不为负数,只需要右移统计1的个数就好了.
一个unsigned,学问不少.