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

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 4

J (5 characters)

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

+/@#:

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

Answer 5

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.

Answer 6

Pyth, 4 bytes

sjQ2

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

Answer 7

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 8

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 9

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 10

Mathematica, 22 18 bytes

Thanks to alephalpha for reminding me of DigitCount.

DigitCount[#,2,1]&

Answer 11

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 12

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 13

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 14

Ruby, 18 bytes

n.to_s(2).count'1'

Answer 15

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

Answer 16

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 17

C#, 45 bytes

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

https://dotnetfiddle.net/kJDgOY

Answer 18

Japt, 3 bytes (non-competitive)

¢¬x

Try it here.

Answer 19

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 20

Pyt, 1 byte

Hooray for built-ins.

Ħ

Try it online!

Non-built-in:

Pyt, 3 bytes

ɓƖŚ

Try it online!

Explanation:

      Implicit input
ɓ     Convert to binary string
Ɩ     Cast as integer
Ś     Sum of digits
      Implicit output

Answer 21

Brachylog, 2 bytes

ḃ+

Try it online!

Just about exactly the Jelly answer.

Answer 22

MathGolf, 2 bytes

âΣ

Try it online!

Explanation

â    convert to binary
 Σ   sum(list), digit sum(int)

Answer 23

K (ngn/k), 4 bytes

+/2\

Try it online!

Convert to base 2, sum up.

Answer 24

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

Answer 25

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.

Answer 26

Octave, 18

sum(dec2bin(s)-48)

Example:

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

Answer 27

GML (Game Maker Language), 21 bytes

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

Answer 28

C# 39 bytes

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

Answer 29

Clojure, 42 bytes

#(count(filter #{\1}(Long/toString % 2)))

Reading right to left, convert to a binary string, convert to a sequence of characters, filter on 1s and count how many you have.

EDITED With help from Sieg

Answer 30

Perl, 21

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

Answer 31

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)

Answer 32

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.

Answer 33

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

Answer 34

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

Answer 35

05AB1E (non-competing), 3 bytes

bSO

Try it online!

Answer 36

16/32-bit x86 assembly, 9 bytes

(based on es1024's answer)

31 C0 D1 E9 10 E0 41 E2 F9

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)
inc cx            ; 41      Increment cx to offset following decrement
loop $-5          ; 75 F9   Jump up to shr cx, 1 if cx-1 is not zero

cx is the 16-bit integer to profile, result is returned in ax.

Answer 37

Pip, 5 bytes

(The language postdates the question, barely.)

1NTBa

Try it online!

With the knowledge that a represents the first command-line argument, this program can be understood quite straightforwardly: 1 iN To-Binary(a). That is, convert a to binary and count the number of 1s.

Answer 38

Stax, 4 bytes

:B|+

Run and debug online!

Explanation

:B|+
:B      Binary digits
  |+    Sum

Answer 39

Japt, 3 bytes

¤è1

Try it

Convert to a binary string and count the 1s.

Answer 40

dc, 25 bytes

[2~rd0<B]dsBx[+z1<S]dsSxp

Try it online!

Two macros. [2~rd0<B]dsBx breaks a decimal value down into binary components by repeatedly dividing by two (using ~ to leave both quotient and remainder on stack) until left with a quotient of zero. After our stack is filled with ones and zeros, [+z1<S]dsSx sums it up by adding the top two values until there's only one value left. p prints our final answer.

Answer 41

Add++, 8 bytes

L,BBBDBs

Try it online!

Surprisingly short for Add++

How it works

L,      ; Define a lambda function
        ; Example argument: 1337
    BB  ; Binary;  STACK = [10100111001]
    BD  ; Digits;  STACK = [[1 0 1 0 0 1 1 1 0 0 1]]
    Bs  ; Sum;     STACK = [6]

Answer 42

Kotlin, 30 bytes

{it.toString(2).sumBy{it-'0'}}

Try it online!

Answer 43

><>, 18 bytes

0$:2%:{+}-2,:@?!n!

Try it online!

Answer 44

cQuents, 6 bytes

uJ$);1

Try it online!

Explanation

:uJ$);1
:            implicit :
              mode: sequence 1 - given input n, output nth term in sequence
             each term in the sequence is

 u   ;1      count(                , 1)
  J )              toBase(     , 2)
   $                      index

Answer 45

Pari/GP, 13 bytes

Pari/GP has a built-in for Hamming weight.

hammingweight

Try it online!

Answer 46

Perl 6, 18 bytes

*.base(2).comb.sum

Works with any nonnegative integer, in fact.

Try it online!

Answer 47

K5, 9 bytes

+/(16#2)\

I used k5's "unpack" overload for \ to split the number into base 2 digits. You can try it online here using oK.

Answer 48

Go, 24

This is an adaptation of the C solution by @steveverrill

n:=0;for;x>0;n++{x&=x-1}

We need to explicitly declare n outside the loop to keep it in scope.

Go requires curly braces as well, and the check in the for loop must be a boolean expression.

http://play.golang.org/p/Z_iuGL5nZ5

Answer 49

WDC 65816, 8 bytes

Assuming 8-bit XY (P.x = 1), the following 8 bytes of object code produce the popcnt of A in X within 145 cycles:

A2 00 4A 90 01 E8 D0 FA

This works on a 65816 whether A is 8-bit (P.m = 1) or 16-bit (P.m = 0), and it has also been tested in a virtual 6502 with 8-bit values. With 16-bit XY on a 65816 (P.x = 0), one more byte is needed: replace A2 00 with A2 00 00.

Assembly source:

  ldx #0       ; A2 00, or A2 00 00 in 16-bit XY mode
loop:
  lsr a        ; 4A    Copy bit 0 of A to carry and shift A right by 1
  bcc zerobit  ; 90 01 If carry is 1, add 1 to X
  inx          ; E8
zerobit:
  bne loop     ; D0 FA If the last ALU result was nonzero, keep counting

The bne instruction branches on the zero flag, which changes whenever an instruction writes to register A, X, or Y. For a 1 bit, inx is the last instruction to write to A, X, or Y, and X is nonzero if there are 1 to 255 bits (only 16 are possible!), so the loop continues. For a 0 bit, lsr a is the last instruction to write to A, X, or Y, and A is nonzero only if there are more bits to count.

Answer 50

perl (35 characters)

$b=sprintf("%b",$d);$c=()=$b=~/1/g;

Answer 51

Clip, 22 chars (25 for full program, or 27 for working with zero)

[Fy?!%lyWOO])Fmy#WilyW

Prefix this with F<some value> to get the answer for that value. Or, for a full program to read from stdin, prefix the code with Fnx. In a previous answer, I golfed a way in Clip to check if something's a power of two. I always return one in that case. Otherwise, increment the result of applying this function (recursively) to 2^(floor(log2(<function parameter>))).

To make this work with zero (returning 0), use (28 chars):

[Fy?!yZ]?!%lyWOO])Fmy#WilyW

Answer 52

Bash, 63 51 47 bytes

[ $1 = 0 ]&&echo 0||echo $[$1%2+`$0 $[$1/2]`]

The shorter the code, the clearer the meaning :).

---

51:

[ $1 -ne 0 ]&&echo $[($1&1)+$($0 $[$1/2])]||echo 0

Recursive script instead of script with recursing function.

---

The "negative-cond || instruction" idiom instead of boring "if cond; then instruction; fi " is our friend here.

Note that echo should return 0 (true), so [ $1 -ne 0 ] && echo $[$[$1&1]+$(n $[$1/2])]

has the logical value of [ $1 -ne 0 ] alone.

Answer 53

Perl 6: 17

The first thing that comes to mind is

[+] 1337.base(2).comb; # returns 6

---

Although this doesn't have any arbitrary limits ( the only limits are how much memory you have, and how long you are willing to wait )

[+] ( uint64.Range.max * 2 + 1 ).base(2).comb; # returns 65

# 340282366920938463463374607431768211455
my $uint128-max = :2( 1 x 128 );
[+] $uint128-max.base(2).comb; # returns 128

my $uint8192-max = :2( 1 x 8192 ); # 2467 digit Int
[+] $uint8192-max.base(2).comb; # returns 8192 (takes about a second currently)

Without making it into a Callable the shortest way to write this is to put the Int into the "default" variable $_. ( .method is always short for $_.method )

$_ = 1337;
[+] .base(2).comb;

given 1337 { # Perl6's with/switch statement
  [+] .base(2).comb
}

[+] .base(2).comb given 1337; # ditto

if 1337 -> $_ { # pointy block
  [+] .base(2).comb
}

If you want to create a Callable you could just put it into a Block.

my $code-ref = {[+] .base(2).comb};
# if it is called with an argument it places it in $_
# if called without an argument uses the $_ from an outer scope

If you really want to call it as a normal subroutine:

my &f={[+] .base(2).comb}; # sub f($_){[+] .base(2).comb}

say f 1337; # 6

$_ = 1337;
say f; # 6

---

Based on your requirements I'd guess that the answer you are looking for is:

[+] .base(2).comb

This assumes that the value is already in $_. It would most likely be the last statement in a subroutine, the right side of an assignment, or an argument to a subroutine or method. ( Otherwise it calculates the result only to throw it away, unless the compiler notices that the result is unused )

---

In case you were wondering [+] 1, 2, 3 can be considered short for (1,2,3).reduce(&[+]).
Where &[+] is short for &infix:< + > the collection of multi subs available in the current scope that are responsible for the numerical infix addition operator +.

Answer 54

ActionScript 3, 17 bytes

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

This is a copy of steveverrill answer, how ever by using AS3, I don't have to put ; at the end of the line, so I save 1 byte.

Also I assume that x and n been initialize already.

Answer 55

O, 7 bytes

H2b~]+o

Explanation:

H        Push input into array
  2b~    Push all the bits of the binary form to the array
     ]+o Add them all up and output the array

Answer 56

TeaScript, 9 bytes (non-competitive)

x÷f»l¦1)n

Try it here.

Answer 57

Seriously, 6 bytes (non-competitive)

This one is fun and neat, and given the number of non-competitive entries it has attracted, I might as well add a Seriously answer.

'12,¡c

Try it online

Explanation:

'12,¡c
   ,     get input
  2 ¡    convert to binary string
'1   c   count the occurrences of "1"
         (implicit print at EOF)

Answer 58

Candy, 15 bytes

I would have thought this would do a bit better, but the lack of an operator to convert numbers to a base 2 string seems to have hurt it. Maybe in a future version of Candy to pull an int from the stack and push 1's and 0's. That would make this one kind of boring, just XS?.

(~A2%h2/LD{)|=Z

The long form is:

while   # stack not empty
  peekA
  pushA    
  digit2
  mod       # get low bit
  popAddZ   # Z = Z + low bit
  digit2
  div
  floor     # integer div 2
  dupl
  if        # if the top of stack is non-zero
endwhile    # NOTE that the endwhile is in an if-then clause
  else
    popA
    pushZ   # NOTE the lack of an endif.
            #  braces and parens are calculated as the
            #  program counter advances over them

Answer 59

C# 45

int o=Convert.ToString(n,2).Count(x=>x=='1');

where o holds the amount of ones and where n is the number.

Alternative and faster C# 6.0 88 bytes

int o=b(n,16).Count(x=>x=='1');
static string b(int v,int l)=>(l>1?b(v>>1,l-1):null)+"01"[v&1];

where the o holds the number of ones and where the n is the number.

Answer 60

Javascript ES6, 35 bytes

a=>a.toString(2).match(/1/g).length

Answer 61

x86 cpu instructions, 30 bytes

56 89 E6 8B 44 04 3D 00 00 74 0F D1 E8 50 E8 EF FF 8B 4C 04 81 E1 01 00 01 C8 5E C2 02 00

meaning and disassembly:

; input in the stack sp+4
; output in ax
;0i,2Ka,4P
f:  
push  si
mov   si,  sp
mov   ax,  [si+4]
cmp   ax,  0
je   .z
shr   ax,  1
push  ax
call  f
mov   cx,  [si+4]
and   cx,  1
add   ax,  cx
.z:  
pop   si
ret 2


0000000F  56                push si
00000010  89E6              mov si,sp
00000012  8B4404            mov ax,[si+0x4]
00000015  3D0000            cmp ax,0x0
00000018  740F              jz 0x29
0000001A  D1E8              shr ax,1
0000001C  50                push ax
0000001D  E8EFFF            call 0xf
00000020  8B4C04            mov cx,[si+0x4]
00000023  81E10100          and cx,0x1
00000027  01C8              add ax,cx
00000029  5E                pop si
0000002A  C20200            ret 0x2
//30

Answer 62

RProgN, 8 Bytes

2 B S ++

Explination

2 B     # Convert to base 2
S       # Convert from string to a stack of individual characters
++      # Sum the stack.

Simple enough, Could be made cheaper if the sugar for sum was single character, instead of double, as ►2BS<SUM> could then be used, saving a byte.

Test Cases

1337:       6.0
16:         1.0
255:        8.0
1236172031: 21.0

Answer 63

LUA 55 bytes

while(i>0)do if(v-i)>=0 then c=c+1;v=v-i;end i=i/2 end

v is the value

i is the max value of an (x)bit Integer, 65535 in this example.

c counts one up, if there's a remainder from (i-l), which means that a one is found.

This is more a simple algorithm than a single statement.