recursion - 计算整数的二进制 1 的递归方法函数

Question

我想编写一个递归方法函数，它以非负整数 n 作为输入并返回 n 上二进制表示中 1 的数量。我被指示使用这样一个事实，即这等于 n//2（整数除法）表示中 1 的数量，如果 n 是奇数，则加 1。

    Usage:
    >>> ones(0)
    0
    >>> ones(1)
    1
    >>> ones(14)
    3

好的，这是我到目前为止得到的代码，但它仍然无法正常工作。无论我输入什么，它都会给我 0。

     def numOnes(n):
     # base case
       if n==0:
          print (0)
       elif n ==1:
          print (1)
     # recursive case
       else:
           return numOnes(n//2)+numOnes(n%2)

谢谢

Answer 1

这些元素你需要自己做：

if integer & 1 == 1: # & is the binary and. & 1 will give the lowest bit
    # there is a 1 in the end

integer = integer // 2 # loose one bit in the end
# or
integer = integer >> 1 # loose one bit in the end

如果您需要更多输入，请告诉我。

您的代码对我有用：

>>> def numOnes(n):
     # base case
       if n==0:
          return (0)
       elif n == 1:
          return (1)
     # recursive case
       else:
           return numOnes(n//2)+numOnes(n%2)


>>> numOnes(0b1100011)
4

Answer 2

对于两个基本情况，您使用print而不是。return修复它，它会工作：

In [2]: numOnes(15842)
Out[2]: 9

In [3]: bin(15842).count('1')
Out[3]: 9