# 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... :/ Feb 13, 2016 at 2:40
• I guess I won't be using Wise for this challenge... :) Mar 31, 2017 at 17:17

## APL, 9 12 characters

+/2|⌊⎕÷2*⍳32


This assumes that the interpreter uses 32-bit integers, and that ⎕IO is set to 0 (meaning that monadic ⍳ begins with 0, rather than 1). I used the 32-bit version of Dyalog APL.

Explanation, from right to left:

• ⍳32 generates a vector of the first 32 integers (as explained before, because ⎕IO is 0, this vector begins with 0).
• * is the power function. In this case, it generates 2 to the power of each element of the vector supplied as its right argument.
• ÷ is the divided-by function. It gives us ⎕ (evaluated user input) divided by each element of the vector to its right (each power of two).
• ⌊ floors each element of the argument to its right.
• 2| gives us the remainder of each element of to its right divided by 2.
• / reduces (folds) its right argument using the function to its left, +.

Not quite 9 characters anymore. :(

Old, rule-breaking version:

+/⎕⊤⍨32/2


Explanation, from right to left:

• 32/2: Replicate 2, 32 times.
• ⍨ commutes the dyadic function to its left, which in this case is ⊤ (i.e., X⊤⍨Y is equivalent to Y⊤X).
• ⊤ is the encode function. It encodes the integer to its right in the base given to its left. Note that, because of the commute operator, the right and left arguments are switched. The base is repeated for the number of digits required, hence 32/2.
• ⎕ is a niladic function that accepts user input and evaluates it.
• +/ reduces (folds) its right argument using +. (We add up the 0's and 1's.)
• Doesn't this break the Built-in base conversion functions contraint? Dec 30, 2011 at 21:18
• Whoops! Missed that one. Dec 30, 2011 at 21:19
• Gah! Thought I'd given myself a fighting chance with my J program! :-) Nice job. Dec 30, 2011 at 23:01
• @Gareth: I didn't realize until reading your explanation just now, but my answer is pretty much identical to yours! I guess that could be expected from APL and J. :) Dec 31, 2011 at 0:42

# Brainbool, 2

,.


The most reasonable interpretation, in my opinion (and what most of the answers use) of "highest number your language is able to handle" is "largest number your language natively supports". Brainbool is a brainfuck derivative that uses bits rather than bytes, and takes input and output in binary (0 and 1 characters) rather than character codes. The largest natively supported number is therefore 1, and the smallest is 0, which have Hamming weights 1 and 0 respectively.

Brainbool was created in 2010, according to Esolang.

• I knew it must have existed, but it took me an hour of sorting through Brainfuck derivatives on Esolang to find Brainbool. Jul 8, 2015 at 2:17
• Wow, this post was before the loophole was created! Mar 14, 2022 at 14:30

# Brainfuck, 53 characters

This was missing an obligatory Brainfuck solution, so I made this one:

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


Takes number from cell 1 and puts the result into cell 6.

Unenrolled and commented version:

[  while n != 0
[  div 2 loop
-
>+<  marker for if/else
[->->>>+<<]  if n != 0 inc n/2
>
[->>>>+<<]  else inc m
<<<
]
>>>>  move n/2 back to n
[-<<<<+>>>>]
<<<<
]


## J, 13 characters

(+ the number of digits in the number)

+/2|<.n%2^i.32


Usage: replace the n in the program with the number to be tested.

Examples:

+/2|<.56432%2^i.32
8
+/2|<.45781254%2^i.32
11
+/2|<.0%2^i.32
0


There's probably a way of rearranging this so the number can be placed at the beginning or end, but this is my first J entry and my head's hurting slightly now.

Explanation(mainly so that I understand it in the future)

i.32 - creates an array of the numbers 1 to 32

2^ - turns the list into the powers of two 1 to 4294967296

n% - divides the input number by each element in the list

<. - rounds all the divison results down to the next integer

2| - same as %2 in most languages - returns 0 if even and 1 if odd

+/ - totals the items in the list (which are now just 1s or 0s)

• I'll be happy to upvote this once it reads from stdin (or whatever equivalent J has). Dec 30, 2011 at 18:51
• The best I could do I think (maybe, depending on figuring out how) is move the input to the end of the program. Standard input isn't mentioned in the question though? Dec 30, 2011 at 21:18
• I'm sorry for not specifying the way of input. It would be unfair to change the rules now, so I'll accept this one. I will mention it next time! Dec 30, 2011 at 22:21
• @pimvdb No problem, it wasn't a complaint. I think with J programs though all you can do is define a verb that operates on the input given it. Not sure how I'd rearrange this to do that though. Maybe JB or one of the other J experts could help me out with that... Dec 30, 2011 at 22:59
• ...and having read some more I now see that I was completely wrong about standard input. Dec 31, 2011 at 10:02

# Python 2.6, 41 characters

t,n=0,input()
while n:t+=n%2;n/=2
print t


note: My other answer uses lambda and recursion and this one uses a while loop. I think they are different enough to warrant two answers.

## Ruby, 38 characters

f=->u{u<1?0:u%2+f[u/2]}
p f[gets.to_i]


Another solution using ruby and the same recursive approach as Steven.

## GolfScript, 17 16 characters

~{.2%\2/.}do]0-,


Edit: new version saves 1 character by using list operation instead of fold (original version was ~{.2%\2/.}do]{+}*, direct count version: ~0\{.2%@+\2/.}do;).

## C, 45

f(n,c){for(c=0;n;n/=2)c+=n%2;printf("%d",c);}


Nothing really special here for golfing in C: implicit return type, implicit integer type for parameters.

## Python 2.6, 45 characters

b=lambda n:n and n%2+b(n/2)
print b(input())

• Can be shortened by two characters by using def instead of a lambda. Dec 31, 2011 at 11:51
• @KonradRudolph: Actually, you lose the advantage once you include the return statement. Dec 31, 2011 at 18:02
• Oops, I forgot that. Stupid. Dec 31, 2011 at 18:06
• You don't need the print b(input()). It is acceptable to return the value and take "input" as arguments for functions. Mar 31, 2017 at 14:27

7

## PHP, 55 (alternative solution)

function b($i){return$i|0?($i%2)+b($i/2):0;}echo b($n);  Again, this assumes that $n holds the value to be tested. This is an alternative because it uses the or-operator to floor the input.

Both solutions work and do not cause notices.

# Ocaml, 45 characters

Based on @Leah Xue's solution. Three spaces could be removed and it's sligthly shorter (~3 characters) to use function instead of if-then-else.

let rec o=function 0->0|x->(x mod 2)+(o(x/2))


# Java 7, 36 bytes

int b(Long a){return a.bitCount(a);}


Because of course this, of all things, is something that Java has a builtin for...

• Doesn't this fit under "built-in base-conversion functions", which are banned? Dec 16, 2016 at 20:22
• @Flp.Tkc I'm not actually doing base-conversion. I have no idea how bitCount operates under the hood.
– Poke
Dec 16, 2016 at 20:29
• this seems like just using a bulitin to do the job, but ok... Dec 16, 2016 at 20:30
• @Flp.Tkc That's... exactly what it is? I'm even including all required libraries (there aren't any). This is demonstrating the strength of the language! related meta
– Poke
Dec 16, 2016 at 20:35

# Mathematica 26

Count[n~IntegerDigits~2,1]


# 386 opcode, 10 Bytes

2BC0                       SUB EAX,EAX
41                         INC ECX
E2F9                       LOOP $-5 C3 RET  Thank Peter Cordes for 1B save and 1B rule save • You can just write a function that returns a value in AL, avoiding the out. Also use 2-byte adc al, 0. But good use of inc/loop as a 3-byte replacement for test ecx,ecx/jnz. And BTW, you could include another version that does popcnt eax, ecx / ret, for CPUs with that feature. Apr 28, 2020 at 23:19 # Vyxall, 49 bits1, 6.125 bytes ʀEṗ'∑?=;f  Try it Online! Brute force solution, so the online interpreter times out. May potentially be made shorter by porting others, but I thought this solution was fun ʀ # range 0..input+1 E # raise 2^n for each value in that range ṗ # powerset ' ; # filtered by ∑ # the sum ?= # is equal to the input? f # flatten # after which the l flag takes the length of the top of the stack and implicitly outputs it  ## Scala, 86 characters object O extends App{def f(i:Int):Int=if(i>0)i%2+f(i/2)else 0 print(f(args(0).toInt))}  Usage: scala O 56432 # R, 53 characters o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan()) Examples: > o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan()) 1: 56432 2: Read 1 item [1] 8 > o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan()) 1: 45781254 2: Read 1 item [1] 11 > o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan()) 1: 0 2: Read 1 item [1] 0  If inputting the number is not part of the character count, then it is 43 characters: o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0} with test cases > o(56432) [1] 8 > o(45781254) [1] 11 > o(0) [1] 0  # OCaml, 52 characters let rec o x=if x=0 then 0 else (x mod 2) + (o (x/2))  # Scheme I polished the rules a bit to add to the challenge. The function doesn't care about the base of the number because it uses its own binary scale. I was inspired by the way analog to numeric conversion works. I just use plain recursion for this: (define (find-ones n) (define (nbits n) (let nbits ([i 2]) (if (< i n) (nbits (* i 2)) i))) (let f ([half (/ (nbits n) 2)] [i 0] [n n]) (cond [(< half 2) i] [(< n i) (f (/ half 2) i (/ n 2))] [else (f (/ half 2) (+ i 1) (/ n 2))])))  Isn't reading a number into binary or printing the number from binary a "builtin base conversion function", thus invalidating every answer above that prints an integer? If you permit reading and printing an integer, like almost all the above answers do, then I'll make claims using a builtin popcount function : ### Haskell, 50 There was a popCount routine added to the Data.Bits module for GHC v7.2.1/v7.4.1 this summer (see tickets concerning the primop and binding). import Data.Bits main=interact$show.popCount.read


I cannot beat the above Python and Perl scores using their GMPY or GMP::Mpz modules for GMP sadly, although GMP does offer a popcount function too.

# 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