-二进制数中最低位1的位置
-二进制数中1的个数
用正整数表示二进制数中最低位1的位置
首先,回顾一下补码。
正数的补码依旧是正数本身,而负数的补码是其原码除符号位外,按位取反后+1得到。
举例:-12=1000 0000 0000 1100(原码)=1111 1111 1111 0011(取反)+1=
1111 1111 1111 0100(补码)。 而正12的二进制为
0000 0000 0000 1100.
这就相当于,-12是12的最低位1之前的所有高位取反而得到的。因为-12转为补码时取反之后加了1,使得低位加一进位。
由此,res=n&(-n),我们只需要将其正负数按位与,即是最低位1的位置。
求二进制数中一的个数
1.利用移位运算符统计
避免使用右移运算符(>>),对负数会陷入死循环,高位符号位不断填充1。
使用左移(<<),每次判断是否为1.
2.高效的方法
我们每次消掉一个1,消多少次就有多少个1。
对于正数,我们将其减一,如12=1100,11=1011,相当于最低位1及其右边都取反,这样子,n=n&(n-1),这样就消掉了最低位的1。
int n=-15,ct=n<0;
n=abs(n);
while(n)
{
n=n&(n-1);
ct++;
}
还有很多其他情况,也有一些巧妙的方法,求二进制中1的个数。不过这些情况都要考虑到字节数,效果不显著有局限性,但也不得不承认有一定的启发性。