面试题15:|面试题15: 二进制中 1 的个数

题目描述

  • 请实现一个函数,输入一个整数,输出该数二进制中 1 的个数
  • 例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2
题目解读
  • 剑指Offer 100
  • 书中对于这道题用二进制解题共计三种思路,由浅入深,引人深思
  • 思路详细解析请认真看书
代码
  • 思路一、可能引起死循环的解法
  • 即可只能求出正数二进制中 1 的个数,如果输入负数则引起死循环(详情请看书)
#include using namespace std; class Solution { public: intNumberOf1(int n) { int count = 0; while(n){ if(n & 1){ count ++; } n = n >> 1; } return count; } }; int main(){ Solution ss; cout<

  • 思路二、常规解法
    为了避免死循环,我们可以不右移输入的数字 n。首先把 n 与 1 做与运算,判断 n 的最低位是不是 1。接着把 1 左移一位得到 2,再和 n 做与运算,就能判断 n 的次低位是不是 1.. ,这样反复左移,每次都能判断 n 的其中一位是不是 1
class Solution { public: intNumberOf1(int n) { int count = 0; unsigned int m = 1; while(m){ if(m & n){ count ++; } m = m << 1; } return count; } };

面试题15:|面试题15: 二进制中 1 的个数
文章图片
面试题15: 二进制中 1 的个数_第1张图片" style="border:1px solid black; ">
  • 思路三、能给面试官带来惊喜的做法
    把一个整数减去 1 ,再和原整数做与运算,会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中又多少个 1,就可以进行多少次这样的操作
class Solution { public: intNumberOf1(int n) { int count = 0; while(n){ count ++; n = n & (n - 1); } return count; } };

面试题15:|面试题15: 二进制中 1 的个数
文章图片
面试题15: 二进制中 1 的个数_第2张图片" style="border:1px solid black; "> 总结展望
  • 以前对于二进制真是应用的少,以后计算数字问题需要加以思考应用.
相关题目
  • 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 using namespace std; intNumberOf1(int n) { int count = 0; while(n){ count ++; n = n & (n-1); } return count; }int main(){ int m = 10; int n = 13; cout<

    推荐阅读