剑指offer刷题（11）：二进制中1的个数

发表于 | 阅读次数:

剑指offer刷题（11）：二进制中1的个数

刷题平台：牛客网

二进制中1的个数

考点：

位运算

1、题目描述

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

2、解题思路

一个数只要不为0，该数的二进制至少有一位为1，然后减去1以后原来最后的1变成0，原来1后面的0全变成1，这样并不会影响其余位置的变化，与原来的数求完与操作我们会发现原来数据中少了一个1，依次进行直到与操作为0为止。

例子：

1
2
3
4
5
6
7
8
9
111000总共有3个1：下面是计算过程：
因为111000不等于0，所以计算标志位count=1;
111000-1=110111,与原来的数据求与操作得到110000；
因为110000不等于0，所以计算标志位conut+1,故count=2；
同理110000-1=101111，与110000求与为100000；
count=3；
100000-1=011111，与100000求与操作000000；
因为000000=0，所以最终的结果为count=3；
故111000总共有3个1.

3、算法实现

C/C++实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         while(n!=0)
         {
             count++;
             n=(n-1)&n;
         }
         return count;
     }
};