下面为大家介绍三种解法,参照剑指offer官方题解,欢迎指正!!!!
1.右移解法
首先抛出来一个例子:

  • 假如我们有整数5,他的二进制表示为 0000 0101, 我们需要统计这个里面1的个数,首先初始化一个计数器 count = 0,不难想到的是我们可以使用 1 & 0000 0101 得到 1,则count += 1,在将5进行右移得到 0000 0010, 与 1 进行与运算,此时为0,计数器不加,继续将5右移一位得到 0000 0001, 1 & 0000 0001 得到1,count += 1,此时count = 2. 我们由此得到最终的结果.
    但我们考虑下如果是负数的情况,我们右移会使最右边的一位变成1而不是0,但是我们使用python进行负数补码的求解的时候,最终的结果是一个正整数,所以可以直接的使用右移的方法,但是其他语言我就不太清楚了,希望指正,代码如下:
    class Solution:
 def NumberOf1(self, n):
     # write code here
     count = 0
     if n < 0:
         n = n & 0xffffffff
     while n:
         if (n & 1):
             count += 1
         n = n >> 1
     return count

2.左移解法

  • 同样上面的例子我们设置一个flag = 1, temp = 0, count = 1,下面我们分析过程:
    我们还是用 0000 0101 和 flag 进行与运算,但这次我们不必将负数进行补码的求解,开始 flag = 1, 与运算后 结果为1 ,则count += 1,temp += 1, 下面我们将flag进行左移,得到 10,再将其与0000 0101 进行与运算,得到 0, temp += 1,......继续一直这样运算下去,直到temp = 32(数字有32位),结束.代码如下:
    class Solution:
  def NumberOf1(self, n):
      # write code here
      temp = 0
      count = 0
      flag = 1
      while temp < 32:
          if flag & n:
              count += 1
          flag = flag << 1
          temp += 1
      return count

3.更精简的运算

  • 还是先抛出一个例子:
    二进制数 1100,当我们将 1100 减去1 之后变成 1011, 将 1011 & 1100 得到1000, 可以发现一个正整数减去1,再和原整数做与运算后,会吧最右边的1变成0,那么一个整数的二进制表示中有多少个1就可以进行多少次这样的运算.但这个方法需要进行负数的补码转换,代码如下:
    class Solution:
def NumberOf1(self, n):
    # write code here
    count = 0
    if n < 0:
        n = n & 0xffffffff
    while n:
        count += 1
        n = n & (n-1)
    return count