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

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 2

Octave, 18

sum(dec2bin(s)-48)

Example:

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

Answer 3

GML (Game Maker Language), 21 bytes

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

Answer 4

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

Perl, 21

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

Answer 6

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 7

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 8

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 9

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 10

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 11

𝔼𝕊𝕄𝕚𝕟, 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 12

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 13

Brachylog, 2 bytes

ḃ+

Try it online!

Just about exactly the Jelly answer.

Answer 14

><>, 18 bytes

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

Try it online!

Answer 15

MathGolf, 2 bytes

âΣ

Try it online!

Explanation

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

Answer 16

K (ngn/k), 4 bytes

+/2\

Try it online!

Convert to base 2, sum up.

Answer 17

C# 38 bytes

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

Answer 18

JavaScript, 19 bytes

f=n=>n&&n%2+f(n>>1)

Try it online!

Nice and simple

Answer 19

Desmos, 40 38 bytes

f(x)=floor(mod(x/2^{[0...x]},2)).total

Try it on Desmos!

-2 bytes thanks to emanresu A

Answer 20

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 21

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 22

perl (35 characters)

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

Answer 23

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 24

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 25

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 26

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 27

TeaScript, 9 bytes (non-competitive)

x÷f»l¦1)n

Try it here.

Answer 28

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 29

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 30

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.