剑指 offer 面试题精选图解 15 . 二进制中1的个数

梦里梦外; 2023-02-15 03:36 78阅读 0赞

## **题目描述** ##

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

### **示例1** ###

> 输入：0x7FFFFFFF  
> 输出：31

### **示例2** ###

> 输入：4055  
> 输出：10

## **题目解析** ##

设置一个 flag ，初始时设置为 1 ，然后与输入的数 n 进行与 `&` 运算，结果不为零，则表明 n 当中与 flag 相同位置的二进制位为 1 ，`count` 加 1，每次 flag 左移一位，直到数 n 所对应的二进制的第一位，执行次数为数 n 转化为二进制之后的位数。

还有一种方法就是面试官喜欢的方式了，仅执行数 n 转化为二进制之后 1 个位数次。

比如 9 的二进制表示为：

![v2-1104fa4e23f23452b3d039671b221f8b\_b.png][v2-1104fa4e23f23452b3d039671b221f8b_b.png]

我们将 9 减 1 ，对应的就是 9 的二进制中最右边的一个 1 变成了 0，其之后的位置全变为 1 .

![v2-e71003218549f133bbcde340896b7e7b\_b.png][v2-e71003218549f133bbcde340896b7e7b_b.png]

然后我们将 8 和 9 进行位与运算，并将结果保存在 `n = n & (n-1)=8` ,然后对 `n` 继续重复上述步骤，直到 `n = 0` 为止。

8 减去 1 为 7：

![v2-3ae55398285df73ba29dd3bfe9d1be21\_b.png][v2-3ae55398285df73ba29dd3bfe9d1be21_b.png]

然后让 8 和 7 进行与运算，结果为 0 ，总共执行 2 次，9 的二进制中 1 的个数为 2.

## **代码实现** ##

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

## **时间复杂度** ##

Solution1 的时间复杂度为数`n` 的二进制位数。

Solution2 的时间复杂度为数`n`的二进制中 1 的个数。

## **知识点** ##

二进制及位运算

[v2-1104fa4e23f23452b3d039671b221f8b_b.png]: https://img-blog.csdnimg.cn/img_convert/ed20bdf875e945308d41fd21d19765be.png
[v2-e71003218549f133bbcde340896b7e7b_b.png]: https://img-blog.csdnimg.cn/img_convert/d2d74684bb22166673ac55a683beffd2.png
[v2-3ae55398285df73ba29dd3bfe9d1be21_b.png]: https://img-blog.csdnimg.cn/img_convert/ca3cb6858208db2a21bec2017f9089dd.png