3
$\begingroup$

I have a recursive function that gives some sequence:

def f(n):   if n <= 0:     return 0   else:     return 1-(n%2)+f(n/2) 

Which returns a number. So I need to say what's the logic in this number, and is some logical explanation to this numbers cause, for ex, the number from this function:

def f(n):   if n <= 0:     return 0   else:     return (n%2)+f(n/2) 

is the sum of digits in the "n" number in binary numerical system representation: n = 12 == 1100 -> so f(12) return 2, cause 1+1+0+0 = 2. But what's the logic in the first function?

2 Answers 2

3

Another way to say it is that the second function is counting ones in the binary representation of $n$. Do a little experimenting with the first function:

$\begin{array}{c|c|r} n&f(n)&n\text{ in binary}\\ \hline 0&0&0\\ 1&0&1\\ 2&1&10\\ 3&0&11\\ 4&2&100\\ 5&1&101\\ 6&1&110\\ 7&0&111\\ 8&3&1000 \end{array}$

It does something very similar to the second function, and once you spot it, you should be able to convince yourself that it really does perform that operation.

  • 0
    Ok, now i got it! Thank you very much2012-05-14
1

Hint: Since (n%2) is being replaced by 1-(n%2), it replaces 1 with 0 and 0 with 1 in the binary representation of $n$.