【面试题010】二进制中1的个数

【面试题010】二进制中1的个数

二进制中1的个数

这个世界上面有10种人，一种人知道二进制，而另一种人不知道二进制……呵呵……

输入一个整数，输出该数二进制表示中1的个数。

方法一：

1除了最右边的一位之外，其他所有位置都是0，如果一个整数与1做与运算的结果是1，表示该整数最右边一位是1，否则是0，

然后这个数字在右移一位，如此循环，可得正解；

数学上除以2，和向右移一位是等价的，但是在计算机学科移位的效率比除法高多了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

using namespace std;

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
        {
            count ++;
        }
        n = n >> 1;
    }
    return count;
}

int main()
{
    cout << NumberOf1(10) << endl;
    return 0;
}

注意是，用这种方法没有办法解决输入的整数是负数的问题，如果是负数就死循环了。

方法二：

为了避免负数的移位问题，其实我们可以把1左移一位，这样子就可以判断n的次低位是不是1……

这样子反复左移，每次都能判断n的其中一位是不是1，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>

using namespace std;

int NumberOf1_1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
        {
            count ++;
        }
        n = n >> 1;
    }
    return count;
}

int NumberOf1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
        {
            count ++;
        }
        flag = flag << 1;
    }
    return count;
}

int main()
{
    cout << NumberOf1_1(10) << endl;
    cout << NumberOf1(10) << endl;
    return 0;
}

方法三：

n减去一个数(1)，如果n不等于0的话，本质就是，把n最右边的1变成0，如果1的右边还有其他0的话，把这些其他的0都变成1；

而这个1他左边的数字都保持不变；

我们发现一个问题，n&(n-1)的结果就是去掉n最后的那个1的过程，太好了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>

using namespace std;

int NumberOf1_1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
        {
            count ++;
        }
        n = n >> 1;
    }
    return count;
}

int NumberOf1_2(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
        {
            count ++;
        }
        flag = flag << 1;
    }
    return count;
}

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++ count;
        n = (n - 1) & n;
    }
    return count;
}

int main()
{
    cout << NumberOf1_1(10) << endl;
    cout << NumberOf1_2(10) << endl;
    cout << NumberOf1(10) << endl;
    return 0;
}

运行结果：

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=NumOf1.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)