32
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
8
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Christopher King
    Commented Mar 17, 2015 at 16:11
  • 10
    \$\begingroup\$ @PyRulez Any number is zero modulo 1. \$\endgroup\$
    – Thomas
    Commented Mar 17, 2015 at 17:18
  • 1
    \$\begingroup\$ Hi, you have chosen a wrong answer as accepted answer (by default tie breaker logic of earliest post). \$\endgroup\$
    – Optimizer
    Commented Mar 18, 2015 at 9:11
  • 6
    \$\begingroup\$ @Thomas I never said it was a helpful tip. \$\endgroup\$
    – Christopher King
    Commented Mar 18, 2015 at 15:40
  • 4
    \$\begingroup\$ 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? \$\endgroup\$
    – Level River St
    Commented Mar 18, 2015 at 15:53

79 Answers 79

Reset to default
1 2
3
0
\$\begingroup\$

Javascript ES6, 35 bytes

a=>a.toString(2).match(/1/g).length
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Stax, 4 bytes

:B|+

Run and debug online!

Explanation

:B|+
:B      Binary digits
  |+    Sum
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Kotlin, 30 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 18 bytes

*.base(2).comb.sum

Works with any nonnegative integer, in fact.

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Japt -x, 3 2 bytes

ì2

Try it here

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Thunno 2 S, 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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

8051 opcode, 10 bytes

    clr a       ; E4
p:  xch a, r1   ; C9    Grab bit from r1
    rlc a       ; 33    and swap with r0
    xch a, r0   ; C8    so bits come from
    xch a, r1   ; C9    r1 and r0 alternately
    addc a, #16 ; 34 10
    jnc p       ; 50 F8 Sixteen additions
    ret         ; 22    to reach carry

Input r0 and r1, output acc

8086 opcode, 9 bytes

0100 31C0          XOR     AX,AX
0102 D1EF          SHR     DI,1
0104 1410          ADC     AL,10
0106 73FA          JNB     0102
0108 C3            RET

Same idea

Improve this answer
\$\endgroup\$
-1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – ATaco
    Commented Oct 10, 2016 at 3:57
  • \$\begingroup\$ Uhm,.. what? You can declare by defining in lua. \$\endgroup\$
    – jawo
    Commented Oct 12, 2016 at 17:59
  • \$\begingroup\$ The declaring of these things must be part of the code. \$\endgroup\$
    – ATaco
    Commented Oct 12, 2016 at 22:04
  • \$\begingroup\$ 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 \$\endgroup\$
    – ATaco
    Commented Oct 12, 2016 at 22:05
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.