Print the amount of ones in a binary number without using bitwise operators

Description

Given a number, print the amount of 1s it has in binary representation.

Input

A number >= 0 in base 10 that won't exceed the highest number your language is able to handle.

Output

The amount of 1s in binary representation.

Winning condition

The shortest code wins.

Disallowed

• Bitwise operators. Other operators, like addition and multiplication, are allowed.
• Built-in base conversion functions.

Examples

Input:     Ouput:

56432      8

Input:     Output:

45781254   11

Input:     Output:

0          0

• Are functions allowed? I want to make a Java solution, but writing full code is too tedious... :/ – HyperNeutrino Feb 13 '16 at 2:40
• I guess I won't be using Wise for this challenge... :) – MildlyMilquetoast Mar 31 '17 at 17:17

Python (48 without spaces, 65 with)

x = int(raw_input())
s = 0
while x:
if x%2:
s+=1
x/=2
print s

• My first ever submission on CodeGolf. Wish I had thought of eliminating the if before I saw @Steve Rumbalski's answer – elssar Dec 30 '11 at 17:43

Op, 23 19 (discontinued language of my invention)

0N[1~!?@2%{1+}2/])I


Here's a commented version:

0 # push a 0 onto the stack
N # read an integer from STDIN onto the stack
[ # begin an infinite loop
1 # push a 1 onto the stack
~ # pop the 1 off the stack, and duplicate the top 1 items (i.e. the read number)
! # pop a number, push 1 if 0 or 0 otherwise (NOT)
? # pop a number, if the number is nonzero...
@ # ... then break out of the infinite loop. Basically, break out when N reaches 0.
2 # push a 2 onto the stack
% # pop number "a" off the stack, then number "b", and push b modulo a.
{ # rotate the stack left
1 # push a 1 onto the stack
+ # pop a and b, and push a + b (increment)
} # rotate the stack right
2 # push a 2 onto the stack
/ # pop number "a" off the stack, then number "b", then push b / a (int)
] # repeat back to start of loop
) # shift the stack right, taking off the 0 and leaving only the result
I # output the result as a number to STDOUT


excel, 35

=LEN(A1)-LEN(SUBSTITUTE(A1,"1",""))

• This solution only provides the number of non-zero symbols in an input, and does not provide for the conversion to base 2, meaning that for the input 511 this provides the output 1 rather than the output 9. You should compare your output to that of =LEN(SUBSTITUTE(DEC2BIN(A1),0,)) (which is disallowed because of the builtin function DEC2BIN) – Taylor Scott Mar 25 '17 at 19:16

GolfScript - 21

~{.2%{0):0;}*2/.}do;0


JavaScript, 575551 50 bytes

a=prompt(b=0);while(a){b+=a%2;a=(a-a%2)/2}alert(b)


Modulo is not bitwise operator ☺

• | is a bitwise operator... – Jamie Jul 8 '15 at 3:49
• I can't golf it further... – Jamie Jul 8 '15 at 3:57
• I think you can replace the while with a for. – lirtosiast Jul 8 '15 at 4:10
• The problem is how? I just don't know ;) – Jamie Jul 8 '15 at 4:14
• for(a=prompt(b=0);a;){...} – HyperNeutrino Jul 17 '17 at 22:32

sed, 100 bytes

:
s/[13579]/&;/g
y/123456789/011223344/
s/;0/5/g
s/;1/6/g
s/;2/7/g
s/;3/8/g
s/;4/9/g
/[1-9]/b
s/0//g


Output is in unary; if you want it in decimal, pipe through wc -c or append the following converter (GNU sed -r):

# unary to decimal
:d
s/;;;;;/v/g
s/vv/x/g
s/x([0-9]|$)/x0\1/ s/;;/b/g s/bb/4/ s/b;/3/ s/v;/6/ s/vb/7/ s/v3/8/ s/v4/9/ y/;bvx/125;/ td  This implements successive division by 2, accumulating carry-out as output. It is able to handle fairly large inputs; for example I tested the all-ones 8192-bit input thus: $ dc <<<'2 8192^1-p' | tr -d '\\\n' | ./4434.sed | wc -c
8192


and the mostly-zeros of similar length:

$dc <<<'2 8192^p' | tr -d '\\\n' | ./4434.sed | wc -c 1  Python 2, 25 bytes lambda n:n and n%2+f(n/2)  Try it online! Pushy, 12 bytes $&2%v2/;O_S#


Try it online!

While the input is bigger than 0, it has its least significant bit (using mod) pushed to the second stack, then it is halved (integer division). Once all bits have been placed on the second stack, it is summed and the result is printed.

SNOBOL4 (CSNOBOL4), 66 bytes

	X =INPUT
I	O =O + REMDR(X,2)
X =GT(X) X / 2	:S(I)
OUTPUT =O
END


Try it online!

JavaScript, 43 Bytes, assuming 1/2/2/2/...=0

for(a=prompt(b=0);a;a/=2)b+=a%2>=1;alert(b)


J, 32 Bytes

There's probably a more mathematical way to do this that doesn't require finding the binary representation, but I thought this was pretty good none the less:

+/@:((}:,(|~2:)@{:,<.@-:@{:)^:])


Explanation:

+/@:((}:,(|~2:)@{:,<.@-:@{:)^:])  | Full program
(                          )  | Convert to binary list:
(                     )^:]   | do n times:
}:                            | Curtail the list
,(|~2:)@{:                  | Append the remainder mod 2 of the item dropped
,<.@-:@{:       | Append the floor of half the item dropped
+/@:                                | Sum


A step by step example:

    (}:,(|~2:)@{:,<.@-:@{:) 7
1 3
^ ^
| |
| Floor 7/2
7 % 2

(}:,(|~2:)@{:,<.@-:@{:) 1 3
1 1 1
^ ^ ^
| | |
| | Floor 3/2
| 3 % 2
The input curtailed

((}:,(|~2:^#)@{:,<.@-:@{:)^:]) 7
1 1 1 0 0 0 0 0

+/@:((}:,(|~2:)@{:,<.@-:@{:)^:]) 7
3


Of course, you would only have to do this Ceil(log2 n) times, but thats a lot harder to calculate than just n.

brainfuck, 34 bytes

>+<[[>-]++[>]+[<]>-]>[-<[->+<]>>]<


Try it online!

At 53 bytes, I thought the existing brainfuck solution was way too long /s. Starting cell contains the number and ends on the number of binary digits in it. Doesn't work for numbers above 255 unless you use an interpreter with larger than 8 bit or infinite cells.

How It Works

>+<[[>-]++[>]+[<]>-] Converts the number to binary
>[-<[->+<]>>]<       Adds all the numbers in the binary together


386 opcode, 12 Bytes

2BC0                       SUB EAX,EAX