Help me

This is a discussion on Help me within the C Programming forums, part of the General Programming Boards category; need c cordings for an algorithm that computes the number of 1's in the binary representation of a non-negative integer ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    5

    Help me

    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.

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Sounds like homework, read http://www.cprogramming.com/tutorial...operators.html

    If you have any specific questions, then ask.

  3. #3
    Registered User
    Join Date
    Aug 2007
    Posts
    5
    Quote Originally Posted by zacs7 View Post
    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....thanks

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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

  6. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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:

    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
    Yeah, I know.... I'm rusty.

    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.

  7. #7
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    And if you make an effort of searching the form may be, you will find number of post related to this topic.

    ssharish2005

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21