题目
思路
这道题看上去是真的很简单,就是类似于进行十进制与二进制转换的笔算方法。不过要注意负数的问题,题目的下边给了这样一点解释:
示例三传入的
n = -3
,而编译器记录时记录的是11111111111111111111111111111101
,以补码形式存储,所以进行有符号移位运算会造成一定的错误,那么选择>>>
无符号右移即可。我想到的思路是获取最后一位是否为1
,加到结果中,然后将n
无符号右移直至最终n = 0
结束循环即可。
代码
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
res += (n & 1);
n = n >>> 1;
}
return res;
}
}
分析
无符号右移保证最后一定会移位变为0
从而结束循环,这是一个比较细节的点。另外,由于java中int
类型为32位
,所以只要想办法遍历每一位,很容易就可以得到最终的结果,类似的方法,通过不同的位运算得到结果可以看这里,每一种方法都是很巧妙的。最后,官方给出了一种优化的位运算:方法 2:位操作的小技巧。代码如下:
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
n &= (n - 1);
res++;
}
return res;
}
}
表面上与遍历每一位的思路一样,但是通过n &= (n - 1)
使得每次循环都会使的最靠后的一个1
变为0
,所以循环的次数只与1
的个数有关,最优复杂度得到了优化。
这里的n &= (n - 1)
操作可以通过两个例子来理解:
3和2
、8和7
- 首先考虑
3和2
这一对,即11 和 10
,他们进行与运算后可以得到结果10
,将最后一位置为0
。 - 然后来看第二组
8和7
,即1000和0111
,这两个数进行与运算得到0000
刚好把最高位的1
变成0
。
当然单纯通过例子不一定很好理解原理,其实可以这样想:n
比n - 1
要大一,也就是n = (n - 1) + 1
,而n - 1
的末尾要么是1,要么是0,是0的情况加一变为1,那么在进行与操作,末尾一个是1一个是0,就会得到最后一位变为0的结果;而末尾是1的情况,加一肯定要进行进位,进位后又会重复这一步骤,即倒数第二位加一,直到第一种情况为止,也就是得到类似于8(1000
)的结果,由于除了最高位,每一位都是1进位上来的,结果一定是0,最高位的1由于原本为0,与运算过后也会变为0,这样就将最靠后一个1变成了0。
总结
位运算真的是个很神奇又很巧妙的东西,官解给出的优化方法也是真的巧妙,学到了很多。
如果文章有写的不对的地方还请指正,感恩相遇~
网友评论