首页 > 其他 > 详细

剑指offer(8)

时间:2019-03-02 17:24:18      阅读:145      评论:0      收藏:0      [点我收藏+]

题目:

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

思路:

  第一反应想到的是把数右移,每一位与1相与,然后判断个数,但是若输入的为负数,会出现死循环现象。

  所以我们设置一个标志量1,首先把输入数与1相与,判断,接着,左移标志量,继续接着判断,直到标志位超出系统位数,全变成0为止,这样就可以避免输入负数,出现死循环的现象。

public class Solution {
    public int NumberOf1(int n) {
        int flag = 1;
        int count = 0;
        while(flag!=0){
            if((n&flag)!=0){
                count++;
            }
            flag=flag<<1;
        }
        return count;
    }
}

  但是这个解法中,如果系统是32位,需要判断32次,接下来的算法中,整数中有几个1就只需循环几次。

  输入数如果不是0,那么至少有一位是0,当我们把这个数减一,若最右边的1在m位,且最后一位是0,那么m-1位至最后位全变成1,m位变为0,例如101000,前文m位即为倒数第四位,当减一时,m位变成0,而m位之后全变成1,此时让这个输入数-1与之前的输入数做与运算,会发现我们是在做“去1”运算,当输入数中有k个1,那么我们完成k次的"去1"运算后,输入数将会变成0。

public class Solution {
    public int NumberOf1(int n) {

         int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}

  

剑指offer(8)

原文:https://www.cnblogs.com/figsprite/p/10461824.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!