Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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
share|improve this question

32 Answers 32

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.)
share|improve this answer
2  
Doesn't this break the Built-in base conversion functions contraint? –  Gareth Dec 30 '11 at 21:18
    
Whoops! Missed that one. –  Dillon Cower Dec 30 '11 at 21:19
    
Gah! Thought I'd given myself a fighting chance with my J program! :-) Nice job. –  Gareth Dec 30 '11 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. :) –  Dillon Cower Dec 31 '11 at 0:42

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)

share|improve this answer
    
I'll be happy to upvote this once it reads from stdin (or whatever equivalent J has). –  Steven Rumbalski Dec 30 '11 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? –  Gareth Dec 30 '11 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! –  pimvdb Dec 30 '11 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... –  Gareth Dec 30 '11 at 22:59
    
...and having read some more I now see that I was completely wrong about standard input. –  Gareth Dec 31 '11 at 10:02

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
  [-<<<<+>>>>]
  <<<<
]
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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;).

share|improve this answer

Python 2.6, 45 characters

b=lambda n:n and n%2+b(n/2) 
print b(input())
share|improve this answer
1  
Can be shortened by two characters by using def instead of a lambda. –  Konrad Rudolph Dec 31 '11 at 11:51
    
@KonradRudolph: Actually, you lose the advantage once you include the return statement. –  Steven Rumbalski Dec 31 '11 at 18:02
    
Oops, I forgot that. Stupid. –  Konrad Rudolph Dec 31 '11 at 18:06

Perl, 45 43 36 Characters

$n=<>;while($n){$_+=$n%2;$n/=2}print

Thanks to Howard for 45->43, and to User606723 for 43->36.

share|improve this answer
    
You might use $n=int($n/2) which 2 characters shorter. –  Howard Dec 30 '11 at 16:28
    
Are we sure we need the int()? $n=<>;while($n){$_+=$n%2;$n/=2}print This will keep looping until $n/2 finally gets close enough to 0, but do we care? ;) –  user606723 Dec 30 '11 at 19:17
    
@user606723 I just tried that out and it seems to work perfectly, at least for every case up to 1000. –  PhiNotPi Dec 30 '11 at 20:38

Perl, 30 chars

$==<>;1while$_+=$=%2,$=/=2;say

Based on PhiNotPi's solution, with some extra golfing. Run with perl -M5.010 to enable the Perl 5.10 say feature.

share|improve this answer
    
Does the $= special variable do anything special in your program, or is it just another ordinary variable? –  PhiNotPi Dec 30 '11 at 20:47
2  
@PhiNotPi: $= only takes integer values, so using it saves me an int. –  Ilmari Karonen Dec 30 '11 at 21:11
    
Shouldn't the command-line arg be part of the char count? –  octatoan May 3 '13 at 10:35
    
@SohamChowdhury: Not per this meta thread. –  Ilmari Karonen May 3 '13 at 13:59

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.

share|improve this answer

Common Lisp, 12 chars

(assuming a 1 char variable name - i.e.: 11 + number length)

It's not a base conversion function, so it should work:

(logcount x)

Examples:

[1]> (logcount 0)
0
[2]> (logcount 1)
1
[3]> (logcount 1024)
1
[4]> (logcount 1023)
10
[5]> (logcount 1234567890123456789012345678901234567890)
68

(Using GNU CLISP.)

share|improve this answer
    
Hm well, not exactly what I had in mind to see as an answer :) I don't think I can accept this. It's basically just another case of this. –  pimvdb Dec 31 '11 at 12:31

JavaScript, 78 72 71 characters

I'll post my initial solution which I came up with before posting the question as well. There is already a much better JavaScript answer though :)

for(n=prompt(a=0),j=1;j<=n;j*=2)for(i=j;i<=n;i+=2*j)n<i+j&&a++;alert(a)

http://jsfiddle.net/Mk8zd/1/

The idea comes from certain "mind reading cards" which enable you to obtain the number someone else has in mind, by showing them cards and let them say on which cards their number is apparent.

It works because each number is a unique combination of 1s / 0s in binary. My solution checks on which "cards" the number is apparent so as to determine how many 1s it has. It's just not very efficient, though...

I found this document which outlines the mind reading technique.

share|improve this answer

Haskell (60 chars)

f n=sum[1|x<-[0..n],odd$n`div`2^x]
main=interact$show.f.read
share|improve this answer

C, 61 60 57 53 characters

void f(x){int i=0;for(;x;x/=2)i+=x%2;printf("%u",i);}

The function body only is 38 characters. Edit: removed bitwise operator Edit: put printf out of the loop as suggested in the comments Edit: switch to K&R declaration; also, this is no longer C99-specific

share|improve this answer
    
I see bitwise!!! –  M. Joanis Dec 31 '11 at 6:51
    
I'm sorry but the AND operator also counts as a bitwise operator. –  pimvdb Dec 31 '11 at 10:43
    
@M.Joanis: duh, thanks for noticing. Fixed. –  Sam Hocevar Dec 31 '11 at 12:30
1  
I think you could spare a few characters if you switched to K&R C. If you're ok with that. –  J B Dec 31 '11 at 13:02
    
You could shorten this by four characters by moving the printf out of the loop. –  marinus Jan 1 '12 at 23:02

JavaScript (42 45 47 49)

for(n=prompt(o=0);n=n/2|0;o+=n%2);alert(o)

Demo: http://jsfiddle.net/hcYdx/4/

Edit 1: remove q and use ~~ for rounding, save 2 chars.

Edit 2: use |0 rounding operator instead of ~~ to save parentheses (2 chars).

Edit 3: simplify n>0 to n and combine with n=n/2|0 to make entire condition; now have wasted statement space :(

share|improve this answer
1  
Isn't the |0 a bitwise operator? –  Vilx- Jan 2 '12 at 15:36
    
Technically yes. But i'm using it purely to round to the nearest int, so I'm not getting any bit-wise benefit :) –  mellamokb Jan 3 '12 at 16:36
    
Smells like bending the rules to me... but I'm not the judge. –  Vilx- Jan 4 '12 at 8:46
    
Input 1 gives output 0. –  Atreys Jan 31 '12 at 16:50

C, 66 characters

main(int n,char **a){printf("%u",__builtin_popcount(atoi(a[1])))};

Note: requires gcc or gcc-compatible compiler (e.g. ICC).

For some CPUs __builtin_popcount compiles to a single instruction (e.g. POPCNT on x86).

share|improve this answer
    
Is it correct that __builtin_popcount actually just implements the counting of 1s itself? If so, although it's not strictly wrong according to the rules I honestly don't think this is a fair entry. –  pimvdb Jan 1 '12 at 15:29
    
You should probably stipulate this in the question if you want to disallow entries that take advantage of built-in capabilities of a given language or compiler. –  Paul R Jan 1 '12 at 15:51
    
This is not legal C++ because in C++ you cannot omit the return type on main, nor use printf without prior include. –  celtschk Feb 5 '12 at 13:39
    
@celtschk: fair point - edited out the C++ –  Paul R Feb 5 '12 at 14:39

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))  
share|improve this answer

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

share|improve this answer

D (70 chars)

int f(string i){int k=to!int(i),r;while(k){if(k%2)r++;k/=2;}return r;}
share|improve this answer

Python (48 without spaces, 65 with)

x = int(raw_input())
s = 0
while x:
    if x%2:
        s+=1
    x/=2
print s
share|improve this answer
    
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

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
share|improve this answer

Shell, 41 chars

(echo obase=2;cat)|bc|tr -d '0\012'|wc -c

I don't think I see any other solutions based on cheap conversion to binary plus counting '1's.

share|improve this answer
    
Honestly I don't know shell, but is the obase=2 indeed not some built-in conversion function? If not then please ignore me, but I just wanted to be sure :) –  pimvdb Dec 30 '11 at 22:55
    
Oops, missed that restriction - I was going by the title. It puts the output of bc in base 2. –  Ben Jackson Dec 30 '11 at 23:45

OCaml, 52 characters

let rec o x=if x=0 then 0 else (x mod 2) + (o (x/2))
share|improve this answer

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))])))
share|improve this answer

PHP, 57

$i=$s=0;for(;$i<log($n,2);){$s+=$n/pow(2,$i++)%2;}echo$s;

This assumes that $n holds the value to be tested.

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.

share|improve this answer

Mathematica 26

Count[n~IntegerDigits~2, 1]
share|improve this answer

dc – 26 chars

This is rather long, mostly due to the lack of loop constructs in dc.

0?[d2%rsi+li2/d0<x]dsxx+p

Keeps adding up the modulo 2 of the number and dividing the number by to until it reaches zero. Can handle arbitrarily long integers.

Example:

$ dc -e '0?[d2%rsi+li2/d0<x]dsxx+p' <<< 127
7
$ dc countones.dc <<< 1273434547453452352342346734573465732856238472384263456458235374653784538469120235
138
share|improve this answer

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.

share|improve this answer

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
share|improve this answer

excel, 35

=LEN(A1)-LEN(SUBSTITUTE(A1,"1",""))
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.