Point-to-offer

剑指offer第十一题：二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

分析

观察以下二进制数，可以看到其中有7个1。

11001011101

（1）正数的补码与原码相同；

（2）负数的符号位为1，其余位为该数绝对值的原码按位取反，然后整个数加1，即为其补码。（补码=原码取反+1）

解题

解法一：相邻与（&）

补充0xffffffff相关知识：

0xffffffff表示的是一个十六进制数

1. 将0xffffffff用十进制数表示 0xffffffff=4294967295

2. 将0xffffffff用二进制数表示

   • 15 用二进制表示为1111
   • 0xffffffff = 1111 1111 1111 1111 1111 1111 1111 1111 (8个F的二进制形式, 一个F占4个字节 )
   • 0xffffffff 就是即32位数都是1的二进制数

0x代表16进制，后面是数字，十进制是4294967295

当出现负数时，与0xffffffff相与（&）再进行计算 （目的是得到32位 二进制数）

举个例子，假设n的值是-3，那么它的32位数二进制原码就是：1000 0000 0000 0000 0000 0000 0000 0011（首位为符号位）

也可以通过以下方式计算出负数的补码：0xffffffff - n + 1

-3的补码：0xffffffff - n + 1 = 1111 1111 1111 1111 1111 1111 1111 1100 = 1111 1111 1111 1111 1111 1111 1111 1101 （-3的二进制中有31个1）

function NumberOf1(n)
{
    var count = 0;
    if(n < 0)
        n = n & 0xffffffff;
    while(n){
        n = n & (n - 1);
        count++;
    }
    return count;
}

解释 n & (n - 1)

// n = -3
while(n){
    n = n & (n - 1);
    count++;
    console.log(n);
}

/* 打印结果如下，数字n，然后与 n-1 进行按位与，你会发现除了最靠右的 1 置零后，其他的高位的 1 没有发生变化，每运行一次，就可以知道有一个 1 。
-4
-8
-16
-32
-64
-128
-256
-512
-1024
-2048
-4096
-8192
-16384
-32768
-65536
-131072
-262144
-524288
-1048576
-2097152
-4194304
-8388608
-16777216
-33554432
-67108864
-134217728
-268435456
-536870912
-1073741824
-2147483648
0
*/

解法二：32次寻找

在64位的系统中，INT是4字节整数，也就是32位整数，我们进行32次的位移并进行判断最右边是否为1，最终可知道1的个数。

function NumberOf1(n)
{
    var count = 0;
    for(var i = 0 ; i < 32; i++){
        if(n % 2 !== 0) count++;
        n = n >> 1;
    }
    return count;
}

解法三：与1查找

把这个数逐次 右移 然后和1 与, 就得到最低位的情况,其他位都为0, 如果最低位是0，和1与 之后依旧是0，如果是1，与之后还是1。 对于32位的整数 这样移动32次 就记录了这个数二进制中1的个数了 。

function NumberOf1(n)
{
    var count = 0;
    for(var i = 0 ; i < 32; i++){
        if(n >> i & 1) count++;
    }
    return count;
}

上一篇：10-矩形覆盖

下一篇：12-数值的整数次方