输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示
初步想法
首先我们第一个想法就是十进制是怎么转化为二进制的呢?我们知道,用十进制数一直除以2直到商为0,得到的余数逆序排列即为二进制数,那么我们很容易想到一个while循环就可以解决问题。 但是,对于负数而言,我们需要表示出它的补码形式,而它们的补码是原码取反加1,情况很复杂不好写算法。下面代码只对非负数有效
public class Solution { public int NumberOf1(int n) { int count = 1; if(n == 0){ return 0; } while(n != 1){ if(n%2 == 1){ count++; } n = n >> 1; } return count; } }
方法1 移位法
我们在按位与时,十进制数会被当成二进制数处理,这时就不需要在分情况了。首先我们考虑用1和该数按位与,不断向右移动该数,代码如下:
public class Solution { public int NumberOf1(int n) { int count = 0; while(n != 0){ if((n&1) == 1){ count++; } n = n>>1; } return count; } }
但由于负数有符号位1,移动过程中会导致运算超时。所以我们考虑向左移动0x01,而该二进制数不动,该方法成功!代码如下:
public class Solution { public int NumberOf1(int n) { int count = 0; int mark = 0x01; while(mark != 0){ if((n&mark) != 0){ count++; } mark = mark<<1; } return count; } }
方法2 技巧法
这个方法比较巧妙,就是用二进制数 & (二进制数-1),每执行一次这样的操作,不仅可以精准定位到最右边的1,而且能将其减去,只要一直执行下去直到为零即可。
public class Solution { public int NumberOf1(int n) { int count = 0; while(n != 0){ n = n & (n-1); count++; } return count; } }
是不是很巧妙呢!