二进制中一的个数

xiaoxiao2021-02-28  37

实现一个函数,输入一个整数,输出该数二进制表示中1的个数,例如把9表示成二进制的1001,有2位是1.因此如果输入9,该函数输出2。 思路1:先判断整数二进制中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位一道最右边,再判断是不是1。这样每次移动一位,直到整个整数变为0为止。问题变成了怎么判断一个整数的最右边是不是1了,这个很简单,只要把整数和1做位与运算看结果是不是0就知道了。1除了最右边的一位之外所有位都是0.如果一个整数与1做与运算的结果是1,表示该整数最右边一位是1,否则是0.但是这种思路当输入是一个负数,因为负数有符号,移位后的最高位会设为1,最后会进入死循环。 思路2:为了避免负数出现的死循环,可以不右移输入的数字n。首先把n和1做与位运算,判断n的最低位是不是为1.接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1,这样反复左移,每次都能判断n的其中一位是不是1.这个解法中循环的次数等于整数二进制的位数,32位的整数需要循环32次。 思路3:介绍一种思路,整数中有几个1就只需要循环几次。经发现,把一个整数减去1,都是把最右边的1变成0.如果它的右边还有0的话,所有的0都变成1,而它左边所有位都保持不变。接下来我们把一个整数和它减去1的结果做位与运算,相当于把最右边的1变为0.那么一个整数中有多少个1就会有多少次这样的操作。

//总结:把一个整数减去1之后再和原来的整数做位于运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。 public class Solution { public int NumberOf1(int n) { int count=0; while(n!=0){ n=(n-1)&n; count++; } return count; } }
转载请注明原文地址: https://www.6miu.com/read-2800160.html

最新回复(0)