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

## 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
.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  # 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 = [10100111001] BD ; Digits; STACK = [[1 0 1 0 0 1 1 1 0 0 1]] Bs ; Sum; STACK = [6]  # Kotlin, 30 bytes {it.toString(2).sumBy{it-'0'}}  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


# Perl 6, 18 bytes

*.base(2).comb.sum


Works with any nonnegative integer, in fact.

Try it online!

# Japt-x, 3 2 bytes

ì2


Try it here

# PARI/GP, 13 bytes

hammingweight

Attempt This Online!

PARI/GP has a built-in for this.

# PARI/GP, 17 bytes

n->sumdigits(n,2)

Attempt This Online!

Another built-in, with a more obvious name.

# PARI/GP, 21 bytes

f(n)=if(n,n%2+f(n\2))

Attempt This Online!

Without built-in.

# 8051 Machine Code, 13 bytes

7B 10 E8 13 50 01 0A BB 08 01 E9 DB F6


Takes the integer in R1 (highest 8 bits) and R0 (lowest 8 bits). Returns the result in R2

    MOV R3, #10        ; 7B 10     - Store 16 since we process a 16 bit number
MOV A, R0          ; E8        - Move the first register to check to A

LAB1:
RRC A              ; 13        - Rotate A through the carry to extract the nth bit
JNC LAB2           ; 50 01     - If the current bit is set (Carry = 1)
INC R2             ; 0A        - Increment the result

LAB2:
CJNE R3, #08, LAB3 ; BB 08 01  - If we are done with the first 8 bits
MOV A, R1          ; E9        - Move R1 into the accumulator

LAB3:
DJNZ R3, LAB1      ; DB F6     - Jump back to LOOP if we have done less than 16 iterations
END



# SMALL, 28 bytes

0->n{x?[x%2=1?n+1->n]x/2->x}


Takes input in variable x and the output will be in variable n.

{
x?

[
x % 2 = 1?
n + 1 -> n
]

x / 2 -> x
}


Repeatedly divides x by two until the number is zero, which means every 1 bit will be moved into its rightmost bit at some point. We then perform a check each loop to see if this bit is a 1 and if so, increment n.

# Thunno 2S, 2 bytes

2B


Attempt This Online!

Convert to a binary list. S flag takes the sum.

### Thunno 2, 3 bytes

ḃ1c


Attempt This Online!

Convert to binary and count the 1s.

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

• Not valid, c is not declared, and will error when (c=c+1) happens, you cannot assume i is a value, and you cannot assume the input is v. Please use the standard io methods. Oct 10, 2016 at 3:57
• Uhm,.. what? You can declare by defining in lua.
– jawo
Oct 12, 2016 at 17:59
• The declaring of these things must be part of the code. Oct 12, 2016 at 22:04
• EG, i=65535 c=0 v = io.read() while(i>0)do if(v-i)>=0 then c=c+1;v=v-i;end i=i/2 end Oct 12, 2016 at 22:05