need c cordings for an algorithm that computes the number of 1's in the binary representation of a non-negative integer n . For example if n = 15 your program should return 4 since the binary representation of 15 is 1111. The program should be a recursive one, based on the following definition of f(n) , the number of 1's in the binary representation of n :
f(n) = f((n-1)/2) + 1 if n is odd
= f(n/2) if n is even
= 0 if n = 0.
Sounds like homework, read http://www.cprogramming.com/tutorial...operators.html
If you have any specific questions, then ask.
this is not a homework im doing a project about that , this problem trouble me a lot..if any one can give me a solustion for this ,it would be a great help for me....thanksOriginally Posted by zacs7
If it's a project, why does it need to be recursive, and why did you post the method?
There are far more efficient methods than the one you've outlined.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
And if it's a project why would you want the solution!? That makes no sense.
It's like having a project to build a car, so you go out and buy one... duh
Oh, this looks like fun! Since I agree with zacs7 over the homework aspect of this, I won't provide you with C code. Sorry, but here's an assembly version of it that works with ye olde Borland's command line tools.... turbo assembly ftw:
Yeah, I know.... I'm rusty.Code:_f proc push ebp ; Create stack frame - step 1.0 mov ebp, esp ; Create stack frame - step 1.1 mov eax, [ebp + 8] ; First param to EAX... eax = n now. or eax, eax ; if eax is 0... jz procfdone ; We're done. Return 0. test eax, 1 ; Is EAX even or odd? jz evennum ; If ZF is set, then the number is even dec eax ; eax--; shr eax, 1 ; eax / 2, quick. push eax ; Pass (n - 1) / 2 as param call _f ; Pass to f() add esp, 4 ; Cleanup stack inc eax ; eax++; jmp procfdone ; We're finished! ;) evennum: shr eax, 1 ; Fast divide push eax ; Pass n / 2 to function call _f ; call _f with (n/2) add esp, 4 ; Clean up stack. procfdone: ; EAX will have return value by now. pop ebp ; Take down stack frame - step 1.0 and 1.1 ret ; Manual return from function/procedure. _f endp
But it does work. Could even assemble it into a .obj file and use it in a C program with the Borland stuff.
And btw, if you're lying about homework, you're being stupid.
And if you make an effort of searching the form may be, you will find number of post related to this topic.
ssharish2005
