剑指offer 14. 二进制中1的个数

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

注意：

• 负数在计算机中用其绝对值的补码来表示。

数据范围

−100≤ 输入整数 ≤100

样例1

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。
1
2
3

样例2

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。
1
2
3
4

方法一：位运算 O(logn)

这题需要用到位运算的知识：

1. 如果 $n$ 的二进制表示最后一位为 $1$ ，则 $res$ ++ 。
2. 每次判断完后，都将 $n$ 往右移 $1$ 位，即消除 $n$ 的二进制表示下的最后一位。

这里需要注意的是，c++ 中如果将负数往右移一位，最高位会自动补 $1$ ，这样循环就永远不会结束。所以我们要先将数字转换成无符号整型，这样每次右移就会在最高位补 $0$ ，循环就可以结束了。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n;
        while (un)   res += un & 1, un >>= 1;
        return res;
    }
};
1
2
3
4
5
6
7
8
9

欢迎大家在评论区交流~