Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a closed formula to the problem $f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1$. So far i have found a solution for $n$, which is the number of power of $2$'s needed to add up to the number starting with the greatest power of $2$. Also $n=$ the number of $1$'s needed to represent $n$ in binary form. So for example $f(12)=2, 2^3 + 2^2 = 12$, $12$ in binary is represented as $1100$, two $1$'s so $n=2$. My problem is i know the process but can't find a simple formula to this problem.

share|improve this question
1  
Are you sure that there is a simpler method than counting the number of $1$s in the binary expansion? –  robjohn Dec 3 '11 at 2:05
1  
A related function is "fusc", a name coined by Dijkstra. See also here. –  Zev Chonoles Dec 3 '11 at 13:36

4 Answers 4

There is no known closed form solution for the number of ones in the binary representation of a number, also known as the Hamming weight of the number. You may want to check out this related question on efficient ways to compute f(n): Best algorithm to count the number of set bits in a 32-bit integer?

share|improve this answer

It's obvious that f(n) = number of 1s in n's binary representation

# the following python code would do
f = lambda x:str(bin(x)).count('1')
f(5)  # 2
f(8)  # 1
f(15) # 4

And for efficiency, the following code in C was given in chapter 5.1 of Hacker's Delight

/* returns number of 1s in x's binary reperesantation */
static inline int cnt1(int x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return x;
}

EDIT: If you want a more mathematical representation, f[x_] := Sum[Floor[Mod[x, 2^(i + 1)]/2^i], {i, 0, Infinity}] in Mathematica looks like a ordinary sum formula. But for a closed form solution, sadly I don't think there exist one.

share|improve this answer
    
@Sean I've edited my answer to add a mathematical looking formula. But a closed form solution may not exist :-( –  Pengyu CHEN Dec 3 '11 at 1:25

$$f\left(\sum\limits_{n=0}^{+\infty}2^ix_i\right)=\sum\limits_{n=0}^{+\infty}x_i,\qquad x_i\in\{0,1\}. $$

share|improve this answer

http://en.wikipedia.org/wiki/Hamming_distance

there is not close formula, but the algorithm can be known review the works of Richard Hamming.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.