Count the number of ones in an unsigned 16-bit integer

Question

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.

Answer 1

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

Answer 2

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

Answer 3

J (5 characters)

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

+/@#:

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

Answer 4

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;

Answer 5

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.

Answer 6

Vyxal, 2 bytes

b∑

Try it Online!

Vyxal s, 1 byte

b

Try it Online!

Answer 7

Pyth, 4 bytes

sjQ2

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

Answer 8

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.

Answer 9

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.

Answer 10

APL (Dyalog Extended), ⁸ 3 bytes

+/⊤

Try it online!

-5 from Adám.

  ⊤ convert to base 2
+/  sum

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

Ruby, 18 bytes

n.to_s(2).count'1'

Answer 15

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.

Answer 16

Mathematica, 22 18 bytes

Thanks to alephalpha for reminding me of DigitCount.

DigitCount[#,2,1]&

Answer 17

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!

Answer 18

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

Answer 19

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

Answer 20

C#, 45 bytes

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

https://dotnetfiddle.net/kJDgOY

Answer 21

Japt, 3 bytes (non-competitive)

¢¬x

Try it here.

Answer 22

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.

Answer 23

05AB1E, 3 bytes

bSO

Try it online!

Answer 24

Factor, 9 bytes

bit-count

Try it online!

Answer 25

Python 3.10+, 13 bytes

int.bit_count

Attempt This Online!

Answer 26

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.

Answer 27

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.

Answer 28

Zsh, 25 bytes

<<<${(c)#$(([##2]$1))//0}

Try it online!  _{27b  30b  35b}

• $(([##2]$1)) convert input $1 to binary
• ${ ... //0} remove 0s
• <<<${(c)#`expr`} print length of `expr`

Answer 29

C# 8, 41 bytes

C# 8.0 add a new overload to ToString function for convert to binary:

1337.ToString("b").Split('1').Length - 1

https://dotnetfiddle.net/Y2H4eT

Thanks so much to @jdt for a best answer in C# 8:

using System;
                
public class Program
{
    public static void Main()
    {
        int n = 1337;
        Console.WriteLine(int.PopCount(n));
    }
}

https://dotnetfiddle.net/GS8qBO

Answer 30

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