Write some statement(s) which will count the number of ones in an unsigned sixteen-bit integer.

For example, if the input is 1337, then the result is 6 because 1337 as a sixteen bit binary number is 0000010100111001, which contains six ones.

  • 1
    Tip: just as the some of digits in a number is congruent to the number mod 9, the some of bits equals the number mod 1. – PyRulez Mar 17 '15 at 16:11
  • 8
    @PyRulez Any number is zero modulo 1. – Thomas Mar 17 '15 at 17:18
  • 1
    Hi, you have chosen a wrong answer as accepted answer (by default tie breaker logic of earliest post). – Optimizer Mar 18 '15 at 9:11
  • 3
    @Thomas I never said it was a helpful tip. – PyRulez Mar 18 '15 at 15:40
  • 2
    Why is this question attracting close votes AFTER most of the answers have been posted? Close voters please indicate your reason in the comments. If it is the acceptance of es1024's (very clever) 4-byte answer which does not comply with standard loopholes (because it uses a builtin) please state that this is the reason. Otherwise, what is it? – Level River St Mar 18 '15 at 15:53

55 Answers 55

up vote 34 down vote accepted

80386 Machine Code, 4 bytes

F3 0F B8 C1

which takes the integer in cx and outputs the count in ax, and is equivalent to:

popcnt ax, cx     ; F3 0F B8 C1

And here is an 11 10 byte solution not using POPCNT:

31 C0 D1 E9 10 E0 85 C9 75 F8

which is equivalent to:

xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
test cx, cx       ; 85 C9   Check if cx == 0
jnz $-6           ; 75 F8   Jump up to shr cx, 1 if not
  • Is this in 32-bit or 16-bit (either real or protected) mode? – FUZxxl Mar 17 '15 at 1:33
  • 2
    @FUZxxl The assembly provided is for 16-bit, though replacing ax and cx with eax and ecx changes it to 32-bit. The bytecode is the same for either. – es1024 Mar 17 '15 at 1:36
  • 1
    @es1024 The byte code is the same if this was compiled in 16-bit mode and the 32-bit version in 32-bit mode. – Cole Johnson Mar 17 '15 at 6:30
  • 2
    Isn't popcnt a builtin and thus falling foul of standard loopholes? Still credit for the second solution though. – Alchymist Mar 17 '15 at 9:37
  • 5
    When you claim the length of the machine code, shouldn't the title be "80386 Machine Code", not "80386 Assembler"? – Kevin Reid Mar 18 '15 at 1:43

Python 2, 17 bytes

bin(s).count('1')

The bin built-in returns the integer converted to a binary string. We then count the 1 digits:

>>> s=1337
>>> bin(s)
'0b10100111001'
>>> bin(s).count('1')
6

J (5 characters)

J has no explicit types. This does the right thing for all integers.

+/@#:
  • +/ the sum
  • @ of
  • #: the base two representation

C,21

for(n=0;x;n++)x&=x-1;

you said "write some statements" (not "a function") so I've assumed the number is supplied in x and the number of 1's is returned in n. If I don't have to initialize n I can save 3 bytes.

This is an adaptation of the famous expression x&x-1 for testing if something is a power of 2 (false if it is, true if it isn't.)

Here it is in action on the number 1337 from the question. Note that subtracting 1 flips the least significant 1 bit and all zeroes to the right.

0000010100111001 & 0000010100111000 = 0000010100111000
0000010100111000 & 0000010100110111 = 0000010100110000
0000010100110000 & 0000010100101111 = 0000010100100000
0000010100100000 & 0000010100011111 = 0000010100000000
0000010100000000 & 0000010011111111 = 0000010000000000
0000010000000000 & 0000001111111111 = 0000000000000000

EDIT: for completeness, here's the naive algorithm, which is one byte longer (and quite a bit slower.)

for(n=0;x;x/=2)n+=x&1;
  • Ref: graphics.stanford.edu/~seander/… – edc65 Mar 17 '15 at 7:29
  • 1
    @edc65 so as it turns out, I reinvented the wheel. At least I saved 2 bytes by omitting the {}. It's such a simple task I shouldn´t be surprised someone already came up with it. – Level River St Mar 17 '15 at 8:33
  • "First published in 1960", impressive. – mbomb007 Mar 23 '15 at 18:35
  • Correction to naive algorithm: for(n=0;x;x/=2)n+=x&1; – Helios Apr 29 '15 at 3:58
  • 1
    @nmxprime the OP asks for unsigned int. for -7 = 11111111 11111111 11111111 11111001 on my 32 bit compiler, I get 30 for the fast algorithm, which is correct. For the naive algorithm, it iterates through -7, -7/2=-3, -3/2=-1, -1/2=0. That gives an incorrect answer. Changing x/=2 to x>>=1 may give the correct answer on some compilers, but C is undefined as to whether a 1 or a 0 is shifted into the empty bit for >> on negative numbers. Those compilers that shift a 1 in will go into an infinite loop. The workaround is to define x as an unsigned int. Then x=-7 loads (1<<32)-7=4294967289 into x. – Level River St Jul 1 '15 at 7:39

Pyth, 4 bytes

sjQ2

The program takes the number whose hamming weight is to be found on STDIN.

Julia, 29 27 19 bytes

n->sum(digits(n,2))

This creates an anonymous function that accepts a single argument, n. To use it, assign it to something like f=n->... and call it like f(1337).

The digits() function, when called with 2 arguments, returns an array of the digits of the input in the given base. So digits(n, 2) returns the binary digits of n. Take the sum of the array and you have the number of ones in the binary representation of n.

  • This can be a lot shorter: Julia has a function count_ones – Andrew Piliser Mar 17 '15 at 18:37
  • @AndrewPiliser: Thanks for the suggestion, but built-in functions which exactly accomplish the task are considered a standard loophole and are frowned upon when not explicitly disallowed. – Alex A. Mar 17 '15 at 18:39

Jelly, non-competing

This answer is non-competing, since the language was created after the challenge was posted.

2 bytes:

BS

Jelly is a new language written by @Dennis, with J-like syntax.

         implicit: function of command-line arguments
B        Binary digits as list
 S       Sum

Try it here.

CJam, 6 bytes

ri2b:+

ri         "Read the input and convert it to integer";
  2b       "Convert the integer into base 2 format";
    :+     "Sum the digits of base 2 form";

Try it online here

Joe, 4 bytes

/+Ba

This is an anonymous function. Ba gives the binary representation of a number and /+ sums it.

   (/+Ba)13
3
   (/+Ba)500
6

Ruby, 18 bytes

n.to_s(2).count'1'

  • 1
    n.to_s(2).count ?1 also works, but is the same length – Piccolo Jul 21 '15 at 5:29

Forth, 48 49 bytes

: c ?dup if dup 1- and recurse 1+ then ;
0 1337 c

If an actual function is needed then the second line becomes

: c 0 swap c ;

and you call it by "1337 c". Forth's relatively verbose control words make this a tough one (actually, they make a lot of these tough).

Edit: My previous version did not handle negative numbers correctly.

Mathematica, 22 18 bytes

Thanks to alephalpha for reminding me of DigitCount.

DigitCount[#,2,1]&
  • @alephalpha thanks, but DigitCount takes another parameter :) – Martin Ender Dec 6 '15 at 11:56

ES6 (34 22 21 bytes):

This is a simple recursive function that can be shortened a bit more. It simply takes a bit and runs itself again:

B=n=>n&&(1&n)+B(n>>1)

Try it on http://www.es6fiddle.net/imt5ilve/ (you need the var because of 'use strict';).

I can't believe I've beaten Fish!!!

The old one:

n=>n.toString(2).split(1).length-1

ES5 (39 bytes):

Both functions can be easily adapted to ES5:

function B(n){return n?(1&n)+B(n>>1):0}

//ungolfed:

function B(number)
{
    if( number > 0 )
    {
        //arguments.callee points to the function itself
        return (number & 1) + arguments.callee( number >> 1 );
    }
    else
    {
        return 0;
    }
}

Old one:

function(n){return n.toString(2).split(1).length-1}

@user1455003 gave me a really great idea, that 'triggered' the smallest one:

function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

I've adapted it to ES6 and made it recursive to shorten a lot!

  • 1
    Here's a smaller 'reguar' javascript function. function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x} – wolfhammer Mar 18 '15 at 19:28
  • @user1455003 Thank you A LOT or your suggestion! I've used it and adapted it to ES6 and shortened a lot. Thank you! – Ismael Miguel Mar 20 '15 at 1:05
  • Your welcome! I like what you did with it. With the recursion regular javascript is down to 39! function B(n){return n?(1&n)+B(n>>1):0} – wolfhammer Mar 23 '15 at 16:46
  • @user1455003 If you want, you can edit the ES5 part and add the byte count to the golfed version. (I think you win reputation with edits). – Ismael Miguel Mar 23 '15 at 17:03
  • @user81655 WOW! It works!!! Thank you a lot! I really knew this could be made shorter – Ismael Miguel Apr 9 '16 at 13:03

><> (Fish), 24 bytes + 2 = 26

0$11.>~n;
2,:?!^:2%:{+}-

The program just does repeated mod 2, subtract and divide until the input number becomes zero, then prints the sum of the mod 2s.

Test with the -v flag, e.g.

py -3 fish.py ones.fish -v 1337
  • For a 16bit integer the codepoint input probably not adequate. (The -v flag version still works.) – randomra Mar 17 '15 at 17:29
  • @randomra Damn, you're right. While Unicode input does work, 16-bit is just a few orders of magnitude out of range... – Sp3000 Mar 17 '15 at 20:24

PHP (38 bytes):

This uses the same aproach as my ES6 answer

<?=count(split(1,decbin($_GET[n])))-1;

This is a full code, you only need to put it in a file and access it over the browser, with the parameter n=<number>.

PHP <4.2 (32 bytes):

This is a little shorter:

<?=count(split(1,decbin($n)))-1;

This only works reliably on PHP<4.2 because the directive register_globals was set to Off by default from PHP4.2 up to PHP5.4 (which was removed by then).

If you create a php.ini file with register_globals=On, this will work.

To use the code, access the file using a browser, with either POST or GET.

@ViniciusMonteiro's suggestion (38/45 bytes):

He gave 2 really good suggestions that have a very interesting use of the function array_sum:

38 bytes:

<?=array_sum(str_split(decbin(1337)));

45 bytes:

<?=array_sum(preg_split('//', decbin(1337)));

This is a really great idea and can be shortened a bit more, to be 36 bytes long:

<?=array_sum(split(1,decbin(1337)));
  • 2
    Or you can use echo array_sum(str_split(decbin(1337))); and you can use too echo array_sum(preg_split('//', decbin(1337))); – Vinicius Monteiro Mar 18 '15 at 15:13
  • 1
    @ViniciusMonteiro Thank you a lot for your suggestion. I really loved it! I've added it to the answer. – Ismael Miguel Mar 18 '15 at 16:02
  • Gain four bytes using <?=substr_count(decbin(1337),"1"); (34 bytes) – Cogicero Jun 14 '16 at 8:21
  • 1
    @Cogicero And you can save even more by removing the quotes: <?=substr_count(decbin(1337),1);. That is a total of 32 bytes. Considering that it is a different-enough code, don't you want to post it as your own answer? I surelly will upvote it! – Ismael Miguel Jun 14 '16 at 8:42
  • @Cogicero It´s only two bytes shorter if you use parametrization: <?=substr_count(decbin($argv[1]),1); (or $_GET[n]; 36 bytes) – Titus Feb 14 '17 at 10:41

R, 24 bytes

sum(intToBits(scan())>0)

scan() reads input from stdin.

intToBits() takes an integer and returns a vector of type raw containing the zeroes and ones of the binary representation of the input.

intToBits(scan())>0 returns a logical vector where each element is TRUE if the corresponding binary vector element is a 1 (since all elements are 0 or 1 and 1 > 0), otherwise FALSE.

In R, you can sum a logical vector to get the number of TRUE elements, so summing the vector of logicals as above gets us what we want.

Note that sum() can't handle raw input directly, hence the workaround using logicals.

  • Wouldn't sum(intToBits(scan())) be the same? – seequ Mar 18 '15 at 18:12
  • @Sieg: Unfortunately no since sum() can't take input of type raw, which is what's returned from intToBits(). – Alex A. Mar 18 '15 at 18:44
  • That is really weird to me. – seequ Mar 18 '15 at 18:46
  • 1
    @Sieg: Yeah, it's weird to me too. Oh well. If every porkchop were perfect, we wouldn't have hotdogs. – Alex A. Mar 18 '15 at 18:48
  • And that's the weirdest metaphor ever. – seequ Mar 18 '15 at 20:05

C#, 45 bytes

Convert.ToString((ushort)15,2).Sum(b=>b-48);

https://dotnetfiddle.net/kJDgOY

  • b-48 is even shorter, AFAIK – ThreeFx Mar 19 '15 at 17:43
  • Correct! :) I'll update. – albertjan Mar 19 '15 at 17:48

Japt, 3 bytes (non-competitive)

¢¬x

Try it here.

  • Man, I never see those dates for some reason. – Mama Fun Roll Dec 4 '15 at 3:32
  • 1
    Haha, Japt is shortest :D BTW, ¢o1 l would work as well. Another interesting approach is -¢¬r-0; ¢¬ splits into array of binary digits, r-0 reduces by subtraction, starting at 0, and - negates the result, making it positive. – ETHproductions Dec 4 '15 at 4:06
  • As of last night, you can now use ¢¬x. – ETHproductions Dec 5 '15 at 16:23

beeswax, 31 27 bytes

Non-competing answer. Beeswax is newer than this challenge.

This solution uses Brian Kherigan’s way of counting set bits from the “Bit Twiddling Hacks” website.

it just runs through a loop, incrementing the bit count, while iterating through number=number&(number-1) until number = 0. The solution only goes through the loop as often as there are bits set.

I could shave off 4 bytes by rearranging a few instructions. Both source code and explanation got updated:

pT_
>"p~0+M~p
d~0~@P@&<
{@<

Explanation:

pT_            generate IP, input Integer, redirect
>"             if top lstack value > 0 jump next instruction,
               otherwise continue at next instruction
  p            redirect if top lstack value=0 (see below)
   ~           flip top and 2nd lstack values
    0+         set top lstack value to 0, set top=top+2nd
      M        decrement top lstack value
       ~       flip top and 2nd lstack values
        p      redirect to lower left
        <      redirect to left
       &       top=top&2nd
      @        flip top and 3rd lstack values
    @P         increment top lstack value, flip top and 3rd values
 ~0~           flip top and 2nd values, set top=0, flip top and 2nd again
d              redirect to upper left
>"p~0+M.....   loop back

  p            if top lstack = 0 at " instruction (see above), redirect
  0            set lstack top to zero (irrelevant instruction)
  <            redirect to the left
 @             flip top and 3rd lstack values
{              output top lstack value as integer (bitcount)

Clone my GitHub repository containing the beeswax interpreter, language spec and examples.

Java, 17 bytes

Works for byte, short, char, and int. Use as a lambda.

Integer::bitCount

Test here

Without using built-ins:

42 bytes

s->{int c=0;for(;s!=0;c++)s&=s-1;return c}

Test here

  • 6
    this is a standard loophole: builtin functions that do exactly what you want are forbidden. – FUZxxl Mar 17 '15 at 1:32
  • @FUZxxl The OP never forbade standard loopholes – Cole Johnson Mar 17 '15 at 6:33
  • 1
    @ColeJohnson Standard loopholes are assumed to be closed by default – es1024 Mar 17 '15 at 7:27
  • 6
    @FUZxxl While es1024 is right that the standard loopholes are closed by default, using built-in functions is currently not an accepted loophole at a vote breakdown of +43/-26. – Martin Ender Mar 17 '15 at 9:11

Clip, 6

2 ways:

cb2nx1

This is a straightforward translation of the requirement: the count of ones in the base-2 representation of number.

r+`b2n

Another method, which takes the sum of the digits of the base-2 representation.

Octave, 18

sum(dec2bin(s)-48)

Example:

octave:1> s=1337
s =  1337
octave:2> sum(dec2bin(s)-48)
ans =  6

GML (Game Maker Language), 21 bytes

for(n=0;x;n/=2)n+=x&1

C# 39 bytes

Convert.ToString(X,2).Count(C=>C=='1');

Perl, 21

$r=grep$v&1<<$_,0..15

PowerShell (51 bytes)

"$([char[]][convert]::ToString($s,2)|%{"+$_"})"|iex

Explanation:
[convert]::ToString($s,2) produces a binary string representation from $s.
[char[]] casts it as a char array and allows us to enumerate each char.
|%{"+$_"} prepends each character with a + sign
"$()" implicitly calls .ToString() on the resulting sub expression
|iex sums the piped string (ie. "+1 +0 +1 +1 +0 +1 +0 +0" = 4)

  • Hiya! Following the same logic you have, why not use the inline -join operator and an implicit .ToString() to achieve 45 bytes with [char[]][convert]::ToString($s,2)-join'+'|iex ... OR, as a different approach use inline -replace operator to achieve 43 bytes with ([convert]::ToString($s,2)-replace0).length – AdmBorkBork Jan 7 '16 at 21:08

Haskell 42 chars

t 0=[]
t n=t(quot n 2)++[rem n 2]
f=sum.t

declares the function f :: Integer -> Integer
use from the interactive interpreter as f <number> or add the line main=print$f <number> to the end of the file.

  • You can save a lot of bytes by directly summing the rem n 2s instead of building a list of it and by using div instead of quot: t 0=0 t n=t(div n 2)+rem n 2 - no f anymore. – nimi Mar 22 '15 at 18:13

Matlab, 13 bytes

de2bi creates a vector of zeros and ones representing the binary number, and sum just returns the sum of all the entries.

sum(de2bi(n))

𝔼𝕊𝕄𝕚𝕟, 4 chars / 11 bytes (non-competitive)

⨭⟦ïⓑ

Try it here (Firefox only).

Explanation

Converts input to binary, splits along chars, and gets sum of resulting array.

05AB1E (non-competing), 3 bytes

bSO

Try it online!

protected by Community Mar 19 '15 at 22:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.