【剑指Offer】二进制中1的个数

Posted on | In ,

题目

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

可能引起死循环的解法

1
2
3
4
5
6
7
8
9
10
11
12
public int NumberOf1(int n) {
    int count = 0;

    while (n != 0){
        if ((n & 1) == 1)
            count++;

        n = n >> 1;
    }

    return count;
}

常规解法

1
2
3
4
5
6
7
8
9
10
11
12
13
public int NumberOf1(int n) {
    int count = 0;
    int flag = 1;

    while (flag != 0){
        if ((n & flag) == flag)
            count++;

        flag = flag << 1;
    }

    return count;
}

能给面试官带来惊喜的解法

1
2
3
4
5
6
7
8
9
10
public int NumberOf1(int n) {
    int count = 0;

    while (n != 0){
        count++;
        n = n & (n - 1);
    }

    return count;
}

相关题目

  1. 用一条语句判断一个整数是不是2的整数次方。一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0.根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0.

  2. 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010，13的二进制表示为1101，需要改变1010中的3位才能得到1101.我们可以分为两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数。