Recursive method function that counts binary 1s of an integer

Question

I want to write a recursive method function that takes a nonnegative integer n as input and returns the number of 1s in the binary representation on n. I am instructed to use the fact that this is equal to the number of 1s in the representation of n//2 (integer division), plus 1 if n is odd.

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

ok so this is the code I got so far, it still doesn't work though. it gives me 0 no matter what I input as n.

     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)

Thank you

You can just write bin(n).count('1'). Do you know it? There is no reasons to make it recursive. Anyway, you should try something yourself. — awesoon
– awesoon, Commented May 28, 2013 at 14:55
If you do integer division by 2, you 'shift' the binary representation of the number to the right by one, losing the right-most bit. For example binary 101 is 5; divide by 2 and binary 10 is 2. — dan
– dan, Commented May 28, 2013 at 16:26

User · Accepted Answer · 2013-05-30 11:15:31Z

3

These elements you need to do it yourself:

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

Tell me if you need more input.

Your code works for me:

>>> 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

edited May 30, 2013 at 11:15

answered May 28, 2013 at 16:13

User

15k3 gold badges44 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Snarre Over a year ago

I updated the code a little bit - still not seeing the problem

Blender · Accepted Answer · 2013-05-29 19:06:56Z

0

You use print instead of return for the two base cases. Fix that and it'll work:

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

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

answered May 29, 2013 at 19:06

Blender

300k55 gold badges462 silver badges511 bronze badges

Collectives™ on Stack Overflow

Recursive method function that counts binary 1s of an integer

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related