24
\$\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.

\$\endgroup\$
  • 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\$ – PyRulez Mar 17 '15 at 16:11
  • 8
    \$\begingroup\$ @PyRulez Any number is zero modulo 1. \$\endgroup\$ – Thomas Mar 17 '15 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 Mar 18 '15 at 9:11
  • 4
    \$\begingroup\$ @Thomas I never said it was a helpful tip. \$\endgroup\$ – PyRulez Mar 18 '15 at 15:40
  • 2
    \$\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 Mar 18 '15 at 15:53

63 Answers 63

1
\$\begingroup\$

05AB1E (non-competing), 3 bytes

bSO

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 2 bytes

ḃ+

Try it online!

Just about exactly the Jelly answer.

\$\endgroup\$
1
\$\begingroup\$

MathGolf, 2 bytes

âΣ

Try it online!

Explanation

â    convert to binary
 Σ   sum(list), digit sum(int)
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Kevin Cruijssen Mar 5 at 15:04
  • \$\begingroup\$ 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. \$\endgroup\$ – maxb Mar 5 at 15:11
  • \$\begingroup\$ I'm getting "Not yet implemented" ValueErrors for all while / do-while loops.. :S Unless I'm doing something wrong.. \$\endgroup\$ – Kevin Cruijssen Mar 5 at 15:28
  • \$\begingroup\$ 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. \$\endgroup\$ – maxb Mar 5 at 16:08
  • 1
    \$\begingroup\$ @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> \$\endgroup\$ – maxb Mar 6 at 13:27
1
\$\begingroup\$

K (ngn/k), 4 bytes

+/2\

Try it online!

Convert to base 2, sum up.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

perl (35 characters)

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

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

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

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.

\$\endgroup\$
0
\$\begingroup\$

TeaScript, 9 bytes (non-competitive)

x÷f»l¦1)n

Try it here.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

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.

\$\endgroup\$
0
\$\begingroup\$

Javascript ES6, 35 bytes

a=>a.toString(2).match(/1/g).length
\$\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.

\$\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
\$\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
\$\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.

\$\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.

\$\endgroup\$
0
\$\begingroup\$

Stax, 4 bytes

:B|+

Run and debug online!

Explanation

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

Japt, 3 bytes

¤è1

Try it

Convert to a binary string and count the 1s.

\$\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.

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

Kotlin, 30 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

><>, 18 bytes

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

Try it online!

\$\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
\$\endgroup\$

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?

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