剑指offer之011-二进制中1的个数

题目描述

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

思路

如果n != 0,n的二进制中至少有一个1

  • 如果1在最低位,n-1 & n得到的数正好将这个1,变成0
  • 如果1不在最低位,n-1 & n得到的数正好将这个1,变成0

因此我们判断n-1 & n能够循环运行的次数就可以判断二进制中有多少个1了。

在python中需要使用c_int()函数不然负数不会变成0.

from ctypes import *
def NumberOf1(n):
    # write code here
    cnt = 0
    while c_int(n).value:
        n = n & (n-1)
        cnt += 1
        print(c_int(n), n)
    return cnt

print(NumberOf1(3))