美文网首页
剑指 offer:11、二进制中1的个数

剑指 offer:11、二进制中1的个数

作者: 云中的Jason | 来源:发表于2019-04-01 19:13 被阅读0次

    11. 二进制中1的个数

    题目描述

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

    解题思路:

    • 思路1:直接去掉二进制中位置最靠后的1。假设n=1100,则n-1=1011,那么n&(n-1)=1000,位置最靠后的1被去掉。 时间复杂度O(M), M为1的个数
    • 思路2:利用标志位遍历int的32位; 时间复杂度O(1), 32次循环

    注:负数右移后,最高位补1,如果右移判断最低位将导致死循环

    解答:

    // 方法1
    class Solution {
    public:
        int NumberOf1(int n) {
            int cnt = 0;
            while(n != 0)
            {
                n = n & (n-1);
                cnt++;
            }
            return cnt;
        }
    };
    // 方法2:
    class Solution {
    public:
         int  NumberOf1(int n) {
             int cnt = 0;
             int flag = 1;
             while(flag != 0)
             {
                 if((n & flag) != 0)
                     ++cnt;
                 flag = flag << 1;
             }
             return cnt;
         }
    };
    

    大家有兴趣可以访问我的个人博客,不定时更新一些内容哦!

    图片来自必应壁纸

    相关文章

      网友评论

          本文标题:剑指 offer:11、二进制中1的个数

          本文链接:https://www.haomeiwen.com/subject/jbjbbqtx.html