0%

剑指offer015 二进制中1的个数

Posted on In Valine:

Problem:

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

Intuition:

这一题考的就是位运算了，这里求解的时候有几个点要注意。首先，千万不要用除法。除法效率比位运算低得多，面试官看到了肯定要扣分。其二，一定要注意负数符号扩展的情况，比如下面这段代码就是错误的

1
2
3
4
5
6
7
8
9
10
public int numberOf1(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) != 0) {
                ++count;
            }
            n = n >> 1;
        }
        return count;
}

因为如果数字是负数的话，符号位是1.我们对原来的数字不断按位右移得到的是0XFFFFFFFF，不但无法得到正确结果还会进入死循环，正确的做法是移动标志位，代码如下。

Solution:

1
2
3
4
5
6
7
8
9
10
11
public int numberOfs1(int n) {
      int count = 0;
      int flag = 1;
      while (flag != 0) {
          if ((n & flag) != 0) {
              ++count;
          }
          flag = flag << 1;
      }
      return count;
  }