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

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.

• 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
• @PyRulez Any number is zero modulo 1. – Thomas Mar 17 '15 at 17:18
• 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
• @Thomas I never said it was a helpful tip. – PyRulez Mar 18 '15 at 15:40
• 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

# 05AB1E (non-competing), 3 bytes

bSO


Try it online!

# 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


# Brachylog, 2 bytes

ḃ+


Try it online!

# MathGolf, 2 bytes

âΣ


Try it online!

## Explanation

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

• Completely unrelated to this answer of yours, but I'm unable to find the MathGolf chat anymore.. Is there an infinite loop or infinite list in MathGolf? – Kevin Cruijssen Mar 5 at 15:04
• I've been stressed out with school and work for the past few months, so the chat must be inactive. There's no implicit infinite loop, but if you can make sure that the top of the stack evaluates to true you could use the do-while-without-pop. Once I feel that I have time to answer questions on a regular basis, I'll ask to have the chat reopened. Right now I'm just building a todo-list of features I want to add. – maxb Mar 5 at 15:11
• I'm getting "Not yet implemented" ValueErrors for all while / do-while loops.. :S Unless I'm doing something wrong.. – Kevin Cruijssen Mar 5 at 15:28
• you should use them like {1}∟ or using the fixed size blocks. It's on my todo-list to have the loop operators also close the block, but it's not implemented as of now. – maxb Mar 5 at 16:08
• @KevinCruijssen Maybe I need to clarify the loop structure a bit better, but the correct implementation would be something like {îo}▲. Your script first does Ä1∟ which will push 1 onto the stack until the memory is full or TIO timeouts, then it would print the length of the loop. Basically, in pseudo code it would be int i = 0; do {i++; stack.push(1);} while (i != 0); print(i). The code would never reach the last part since the loop is infinite. Basically, loops are constructed as {<loop code>}<loop operator> – maxb Mar 6 at 13:27

# K (ngn/k), 4 bytes

+/2\


Try it online!

Convert to base 2, sum up.

# 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

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

perl (35 characters)

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


# Bash, 6351 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. # 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 +. # 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  # 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  # 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. # TeaScript, 9 bytes (non-competitive) x÷f»l¦1)n  Try it here. ## 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)  # 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  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. # Javascript ES6, 35 bytes a=>a.toString(2).match(/1/g).length  ## 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. 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  # 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  ## 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.

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

# Stax, 4 bytes

:B|+


Run and debug online!

## Explanation

:B|+
:B      Binary digits
|+    Sum


# Japt, 3 bytes

¤è1


Try it

Convert to a binary string and count the 1s.

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

# 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 = 
BD  ; Digits;  STACK = [[1 0 1 0 0 1 1 1 0 0 1]]
Bs  ; Sum;     STACK = 


# Kotlin, 30 bytes

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


Try it online!

0$:2%:{+}-2,:@?!n!  Try it online! # 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


## 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?