32
\$\begingroup\$

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.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Mar 17, 2015 at 16:11
  • 10
    \$\begingroup\$ @PyRulez Any number is zero modulo 1. \$\endgroup\$
    – Thomas
    Mar 17, 2015 at 17:18
  • 1
    \$\begingroup\$ Hi, you have chosen a wrong answer as accepted answer (by default tie breaker logic of earliest post). \$\endgroup\$
    – Optimizer
    Mar 18, 2015 at 9:11
  • 6
    \$\begingroup\$ @Thomas I never said it was a helpful tip. \$\endgroup\$ Mar 18, 2015 at 15:40
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ Mar 18, 2015 at 15:53

77 Answers 77

39
\$\begingroup\$

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
\$\endgroup\$
8
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – es1024
    Mar 17, 2015 at 1:36
  • 2
    \$\begingroup\$ @es1024 The byte code is the same if this was compiled in 16-bit mode and the 32-bit version in 32-bit mode. \$\endgroup\$
    – Cole Tobin
    Mar 17, 2015 at 6:30
  • 2
    \$\begingroup\$ Isn't popcnt a builtin and thus falling foul of standard loopholes? Still credit for the second solution though. \$\endgroup\$
    – Alchymist
    Mar 17, 2015 at 9:37
  • 5
    \$\begingroup\$ When you claim the length of the machine code, shouldn't the title be "80386 Machine Code", not "80386 Assembler"? \$\endgroup\$
    – Kevin Reid
    Mar 18, 2015 at 1:43
  • 1
    \$\begingroup\$ 85 C9 75 F8 => 41 E2 F9? \$\endgroup\$
    – l4m2
    Mar 14, 2018 at 8:32
15
\$\begingroup\$

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
\$\endgroup\$
0
12
\$\begingroup\$

J (5 characters)

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

+/@#:
  • +/ the sum
  • @ of
  • #: the base two representation
\$\endgroup\$
11
\$\begingroup\$

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;
\$\endgroup\$
7
  • \$\begingroup\$ Ref: graphics.stanford.edu/~seander/… \$\endgroup\$
    – edc65
    Mar 17, 2015 at 7:29
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Mar 17, 2015 at 8:33
  • \$\begingroup\$ "First published in 1960", impressive. \$\endgroup\$
    – mbomb007
    Mar 23, 2015 at 18:35
  • \$\begingroup\$ Correction to naive algorithm: for(n=0;x;x/=2)n+=x&1; \$\endgroup\$
    – Helios
    Apr 29, 2015 at 3:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jul 1, 2015 at 7:39
8
\$\begingroup\$

Jelly, 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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ What is this BS‽ ;-) \$\endgroup\$
    – Adám
    Mar 23, 2021 at 6:29
4
\$\begingroup\$

Pyth, 4 bytes

sjQ2

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

\$\endgroup\$
4
\$\begingroup\$

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.

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

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This can be a lot shorter: Julia has a function count_ones \$\endgroup\$
    – Andrew
    Mar 17, 2015 at 18:37
  • \$\begingroup\$ @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. \$\endgroup\$
    – Alex A.
    Mar 17, 2015 at 18:39
4
+100
\$\begingroup\$

APL (Dyalog Extended), 8 3 bytes

+/⊤

Try it online!

-5 from Adám.

  ⊤ convert to base 2
+/  sum
\$\endgroup\$
1
  • 2
    \$\begingroup\$ While this is as good as it gets in Vanilla, Extended has +/⊤ \$\endgroup\$
    – Adám
    Mar 23, 2021 at 5:24
4
\$\begingroup\$

Rust, 15 bytes

u16::count_ones

Try it online!

Rust is better than C because count_ones is shorter than __builtin__popcount :)

Every built-in integer type (unsigned or signed, 8/16/32/64/128 bits) supports this method. Since the challenge specifically asks for unsigned 16 bit integers, we use u16 here. Also, while the method is usually called in the form of some_number.count_ones(), u16::count_ones(some_number) is also a valid syntax for calling the same function.

\$\endgroup\$
4
\$\begingroup\$

Vyxal, 2 bytes

b∑

Try it Online!

Vyxal s, 1 byte

b

Try it Online!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Ruby, 18 bytes

n.to_s(2).count'1'

\$\endgroup\$
2
  • 1
    \$\begingroup\$ n.to_s(2).count ?1 also works, but is the same length \$\endgroup\$
    – Piccolo
    Jul 21, 2015 at 5:29
  • 1
    \$\begingroup\$ 2019 version: n.digits(2).sum / 15 bytes \$\endgroup\$
    – G B
    Mar 4, 2019 at 13:44
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 22 18 bytes

Thanks to alephalpha for reminding me of DigitCount.

DigitCount[#,2,1]&
\$\endgroup\$
1
  • \$\begingroup\$ @alephalpha thanks, but DigitCount takes another parameter :) \$\endgroup\$ Dec 6, 2015 at 11:56
3
\$\begingroup\$

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!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Here's a smaller 'reguar' javascript function. function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x} \$\endgroup\$
    – wolfhammer
    Mar 18, 2015 at 19:28
  • \$\begingroup\$ @user1455003 Thank you A LOT or your suggestion! I've used it and adapted it to ES6 and shortened a lot. Thank you! \$\endgroup\$ Mar 20, 2015 at 1:05
  • \$\begingroup\$ 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} \$\endgroup\$
    – wolfhammer
    Mar 23, 2015 at 16:46
  • \$\begingroup\$ @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). \$\endgroup\$ Mar 23, 2015 at 17:03
  • 1
    \$\begingroup\$ (1&n) => n%2? \$\endgroup\$
    – l4m2
    Mar 14, 2018 at 8:38
3
\$\begingroup\$

Python, 72 26 bytes

Thanks to mathcat for -12 -27 -36 bytes through various simplifications!

lambda a:bin(a).count('1')

Well, you said statements...

\$\endgroup\$
6
  • \$\begingroup\$ Hi, this can be reduced to 60 bytes by using tabs than spaces and short if. \$\endgroup\$
    – math scat
    Feb 5, 2022 at 16:14
  • \$\begingroup\$ Actually, 35 bytes by using count. \$\endgroup\$
    – math scat
    Feb 5, 2022 at 16:16
  • 1
    \$\begingroup\$ Sorry for these comments, but 26 bytes as it is allowed to use a function (unless specified in the challenge) \$\endgroup\$
    – math scat
    Feb 5, 2022 at 16:20
  • \$\begingroup\$ @mathcat I still have a lot to learn... \$\endgroup\$
    – Oliver
    Feb 5, 2022 at 16:45
  • \$\begingroup\$ Maybe you can look through this post, there are a lot of tips to golf python code there :) \$\endgroup\$
    – math scat
    Feb 5, 2022 at 17:22
2
\$\begingroup\$

><> (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
\$\endgroup\$
2
  • \$\begingroup\$ For a 16bit integer the codepoint input probably not adequate. (The -v flag version still works.) \$\endgroup\$
    – randomra
    Mar 17, 2015 at 17:29
  • \$\begingroup\$ @randomra Damn, you're right. While Unicode input does work, 16-bit is just a few orders of magnitude out of range... \$\endgroup\$
    – Sp3000
    Mar 17, 2015 at 20:24
2
\$\begingroup\$

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)));
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Or you can use echo array_sum(str_split(decbin(1337))); and you can use too echo array_sum(preg_split('//', decbin(1337))); \$\endgroup\$ Mar 18, 2015 at 15:13
  • 1
    \$\begingroup\$ @ViniciusMonteiro Thank you a lot for your suggestion. I really loved it! I've added it to the answer. \$\endgroup\$ Mar 18, 2015 at 16:02
  • \$\begingroup\$ Gain four bytes using <?=substr_count(decbin(1337),"1"); (34 bytes) \$\endgroup\$
    – Cogicero
    Jun 14, 2016 at 8:21
  • 1
    \$\begingroup\$ @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! \$\endgroup\$ Jun 14, 2016 at 8:42
  • \$\begingroup\$ @Cogicero It´s only two bytes shorter if you use parametrization: <?=substr_count(decbin($argv[1]),1); (or $_GET[n]; 36 bytes) \$\endgroup\$
    – Titus
    Feb 14, 2017 at 10:41
2
\$\begingroup\$

C#, 45 bytes

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

https://dotnetfiddle.net/kJDgOY

\$\endgroup\$
2
  • \$\begingroup\$ b-48 is even shorter, AFAIK \$\endgroup\$
    – ThreeFx
    Mar 19, 2015 at 17:43
  • \$\begingroup\$ Correct! :) I'll update. \$\endgroup\$
    – albertjan
    Mar 19, 2015 at 17:48
2
\$\begingroup\$

Japt, 3 bytes (non-competitive)

¢¬x

Try it here.

\$\endgroup\$
3
  • \$\begingroup\$ Man, I never see those dates for some reason. \$\endgroup\$ Dec 4, 2015 at 3:32
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Dec 4, 2015 at 4:06
  • \$\begingroup\$ As of last night, you can now use ¢¬x. \$\endgroup\$ Dec 5, 2015 at 16:23
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 3 bytes

bSO

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Factor, 9 bytes

bit-count

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3.10+, 13 bytes

int.bit_count

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 10 7 bytes

{+/2\x}

Try it online!

Thanks @coltim for -3 bytes by suggesting me that I can just take the sum instead of the count of 1s

Cast the integer into base 2, then sum.

\$\endgroup\$
1
  • \$\begingroup\$ Rather than removing the 0s and taking the count, could you just take the sum instead? It would then be straightforward to make it tacit. \$\endgroup\$
    – coltim
    May 15, 2022 at 17:57
2
\$\begingroup\$

BitCycle, 5 bytes

?+
 !

Online Interpreter

Kind of cheaty, as it inputs in binary and outputs in unary. These are the only two I/O formats this language really can handle, but it's also pretty trivial.


Explanation:

? Take input

+ Send all 0 bits up (deleting them) and all 1 bits down.

! Output all bits that arrive here.

\$\endgroup\$
1
  • \$\begingroup\$ Isn't this 5? I think you forgot the newline \$\endgroup\$
    – Seggan
    Oct 3, 2022 at 16:10
1
\$\begingroup\$

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

\$\endgroup\$
4
  • 7
    \$\begingroup\$ this is a standard loophole: builtin functions that do exactly what you want are forbidden. \$\endgroup\$
    – FUZxxl
    Mar 17, 2015 at 1:32
  • \$\begingroup\$ @FUZxxl The OP never forbade standard loopholes \$\endgroup\$
    – Cole Tobin
    Mar 17, 2015 at 6:33
  • 1
    \$\begingroup\$ @ColeJohnson Standard loopholes are assumed to be closed by default \$\endgroup\$
    – es1024
    Mar 17, 2015 at 7:27
  • 6
    \$\begingroup\$ @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. \$\endgroup\$ Mar 17, 2015 at 9:11
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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