剑指offer：二进制中1的个数

2020-04-02

题目链接

NowCoder

题目描述

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

解题思路（by myself）

首先要搞清楚什么是补码。正数的补码是其本身，负数的补码是对应正数的二进制码取反加1。在计算机中，二进制码的第一位表示符号位，符号位为 1 表示负数，符号位为 0 表示正数。

具体来说，-3 对应的正数是 011，011取反得到 100，加 1 得到 101，因此 -3 对应的二进制码为 101。

在 32 位计算机中，整数型变量存储为 32 bit，因此我在编程时，先初始化长度为 32 的 int 数组，记录每一个 0/1 位。具体解法如下：

class Solution {
public:
     int  NumberOf1(int n) {
         int* bits = new int[32];
         for (int i = 0; i < 32; i++) bits[i] = 0;
         if (n < 0) {
             n = -n;
             bits[0] = 1;
         }
         int current = 31;
         while (n >= 1) {
             bits[current--] = n % 2;
             n = n / 2;
         }
         if (bits[0] == 1) {
             for (int i = 1; i < 32; i++) bits[i] = 1 - bits[i];
         }
         if (bits[0] == 1) {
             int add = 1;
             current = 31;
             while (add != 0 && current != 0) {
                 bits[current] = bits[current] + add;
                 if (bits[current] == 2) {
                     bits[current] = 0;
                     add = 1;
                     current--;
                 } else {
                     add = 0;
                 }
             }
         }
         int ans = 0;
         for (int i = 0; i < 32; i++) {
             if (bits[i] == 1) ans += 1;
         }
         return ans;
     }
};

解题思路（by others）

虽然上述解法可以 AC，但是代码极其不简洁，于是参考学习了其他人的解法。

n&(n-1)

该位运算去除 n 的位级表示中最低的那一位 1。

1
2
3

n       : 10110100
n-1     : 10110011
n&(n-1) : 10110000

时间复杂度：O(M)，其中 M 表示 1 的个数。

class Solution {
public:
     int  NumberOf1(int n) {
         int cnt = 0;
        while (n != 0) {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
};