题目描述
- 请实现一个函数，输入一个整数，输出该数二进制中 1 的个数
- 例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2
题目解读
- 剑指Offer 100
- 书中对于这道题用二进制解题共计三种思路，由浅入深，引人深思
- 思路详细解析请认真看书
代码
- 思路一、可能引起死循环的解法
- 即可只能求出正数二进制中 1 的个数，如果输入负数则引起死循环(详情请看书)
#include<iostream>
using namespace std;
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n){
if(n & 1){
count ++;
}
n = n >> 1;
}
return count;
}
};
int main(){
Solution ss;
cout<<ss.NumberOf1(-9)<<endl;
}
- 思路二、常规解法
为了避免死循环，我们可以不右移输入的数字 n。首先把 n 与 1 做与运算，判断 n 的最低位是不是 1。接着把 1 左移一位得到 2，再和 n 做与运算，就能判断 n 的次低位是不是 1.. ，这样反复左移，每次都能判断 n 的其中一位是不是 1
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int m = 1;
while(m){
if(m & n){
count ++;
}
m = m << 1;
}
return count;
}
};
- 思路三、能给面试官带来惊喜的做法
把一个整数减去 1 ，再和原整数做与运算，会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中又多少个 1，就可以进行多少次这样的操作
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n){
count ++;
n = n & (n - 1);
}
return count;
}
};
总结展望
- 以前对于二进制真是应用的少，以后计算数字问题需要加以思考应用.
相关题目
- 1，用一条语句判断一个整数是不是 2 的整数次方。
一个整数如果是 2 的整数次方，那么它的二进制中有且只有一位是 1，而其他所有位都是 0
根据前面的分析，把这个整数减去 1 之后再和它自己做与运算，这个整数中唯一的 1 就会变成 0
bool aa(int n){
bool result = false;
if(n&(n-1) == 0){
result = true;
}
return result;
}
- 2，输入两个整数 m 和 n，计算需要改变 m 的二进制表示中的多少位才能得到 n。比如 10 的二进制表示为 1010，13的二进制表示为 1101 ，需要改变 1010 中的 3 位数才能得到 1101.
我们可以分为两步解决这个问题：第一步求这两个数的异或；第二步统计异或结果中 1 的个数
#include <iostream>
using namespace std;
int NumberOf1(int n) {
int count = 0;
while(n){
count ++;
n = n & (n-1);
}
return count;
}
int main(){
int m = 10;
int n = 13;
cout<<NumberOf1(m^n)<<endl;
}
