没有输出的输入是不完整的

0%

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

发表于 分类于
本文字数： 639 阅读时长 ≈ 1 分钟

本文为剑指 offer 系列第十三篇。
主要知识点为进制转化和位运算以及数据在计算机中的存储方式，解题方式比较巧妙。

题目描述

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

解题思路

思路1

我们知道在计算机中数据是以二进制0和1进行存储的，所以我们可以通过1和这个数据的每一位进行&运算来计算原来数据中1的个数。

思路2

通过n = n&(n-1)这个运算会消掉n的二进制表示中最右侧的1，只要判断多少次之后n变成0即可计算出原来n中有多少位1.

解题代码

思路1代码

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

时间复杂度为O(n),空间复杂度为O(1)

思路2代码

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

时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！