14
\$\begingroup\$

Description

Given a number, print the amount of 1s it has in binary representation.

Input

A number >= 0 in base 10 that won't exceed the highest number your language is able to handle.

Output

The amount of 1s in binary representation.

Winning condition

The shortest code wins.

Disallowed

  • Bitwise operators. Other operators, like addition and multiplication, are allowed.
  • Built-in base conversion functions.

Examples

Input:     Ouput:

56432      8


Input:     Output:

45781254   11


Input:     Output:

0          0
\$\endgroup\$
  • \$\begingroup\$ Are functions allowed? I want to make a Java solution, but writing full code is too tedious... :/ \$\endgroup\$ – HyperNeutrino Feb 13 '16 at 2:40
  • 1
    \$\begingroup\$ I guess I won't be using Wise for this challenge... :) \$\endgroup\$ – MildlyMilquetoast Mar 31 '17 at 17:17

48 Answers 48

0
\$\begingroup\$

Python (48 without spaces, 65 with)

x = int(raw_input())
s = 0
while x:
    if x%2:
        s+=1
    x/=2
print s
\$\endgroup\$
  • \$\begingroup\$ My first ever submission on CodeGolf. Wish I had thought of eliminating the if before I saw @Steve Rumbalski's answer \$\endgroup\$ – elssar Dec 30 '11 at 17:43
0
\$\begingroup\$

Op, 23 19 (discontinued language of my invention)

0N[1~!?@2%{1+}2/])I

Here's a commented version:

0 # push a 0 onto the stack
N # read an integer from STDIN onto the stack
[ # begin an infinite loop
    1 # push a 1 onto the stack
    ~ # pop the 1 off the stack, and duplicate the top 1 items (i.e. the read number)
    ! # pop a number, push 1 if 0 or 0 otherwise (NOT)
    ? # pop a number, if the number is nonzero...
    @ # ... then break out of the infinite loop. Basically, break out when N reaches 0.
    2 # push a 2 onto the stack
    % # pop number "a" off the stack, then number "b", and push b modulo a.
    { # rotate the stack left
    1 # push a 1 onto the stack
    + # pop a and b, and push a + b (increment)
    } # rotate the stack right
    2 # push a 2 onto the stack
    / # pop number "a" off the stack, then number "b", then push b / a (int)
] # repeat back to start of loop
) # shift the stack right, taking off the 0 and leaving only the result
I # output the result as a number to STDOUT
\$\endgroup\$
0
\$\begingroup\$

excel, 35

=LEN(A1)-LEN(SUBSTITUTE(A1,"1",""))
\$\endgroup\$
  • 1
    \$\begingroup\$ This solution only provides the number of non-zero symbols in an input, and does not provide for the conversion to base 2, meaning that for the input 511 this provides the output 1 rather than the output 9. You should compare your output to that of =LEN(SUBSTITUTE(DEC2BIN(A1),0,)) (which is disallowed because of the builtin function DEC2BIN) \$\endgroup\$ – Taylor Scott Mar 25 '17 at 19:16
0
\$\begingroup\$

GolfScript - 21

~{.2%{0):0;}*2/.}do;0
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 57 55 51 50 bytes

a=prompt(b=0);while(a){b+=a%2;a=(a-a%2)/2}alert(b)

Modulo is not bitwise operator ☺

\$\endgroup\$
  • \$\begingroup\$ | is a bitwise operator... \$\endgroup\$ – Jamie Jul 8 '15 at 3:49
  • \$\begingroup\$ I can't golf it further... \$\endgroup\$ – Jamie Jul 8 '15 at 3:57
  • \$\begingroup\$ I think you can replace the while with a for. \$\endgroup\$ – lirtosiast Jul 8 '15 at 4:10
  • \$\begingroup\$ The problem is how? I just don't know ;) \$\endgroup\$ – Jamie Jul 8 '15 at 4:14
  • \$\begingroup\$ for(a=prompt(b=0);a;){...} \$\endgroup\$ – HyperNeutrino Jul 17 '17 at 22:32
0
\$\begingroup\$

sed, 100 bytes

:
s/[13579]/&;/g
y/123456789/011223344/
s/;0/5/g
s/;1/6/g
s/;2/7/g
s/;3/8/g
s/;4/9/g
/[1-9]/b
s/0//g

Output is in unary; if you want it in decimal, pipe through wc -c or append the following converter (GNU sed -r):

# unary to decimal
:d
s/;;;;;/v/g
s/vv/x/g
s/x([0-9]|$)/x0\1/
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td

This implements successive division by 2, accumulating carry-out as output. It is able to handle fairly large inputs; for example I tested the all-ones 8192-bit input thus:

$ dc <<<'2 8192^1-p' | tr -d '\\\n' | ./4434.sed | wc -c
8192

and the mostly-zeros of similar length:

$ dc <<<'2 8192^p' | tr -d '\\\n' | ./4434.sed | wc -c
1
\$\endgroup\$
0
\$\begingroup\$

Python 2, 25 bytes

lambda n:n and n%2+f(n/2)

Try it online!

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

Pushy, 12 bytes

$&2%v2/;O_S#

Try it online!

While the input is bigger than 0, it has its least significant bit (using mod) pushed to the second stack, then it is halved (integer division). Once all bits have been placed on the second stack, it is summed and the result is printed.

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

SNOBOL4 (CSNOBOL4), 66 bytes

	X =INPUT
I	O =O + REMDR(X,2)
	X =GT(X) X / 2	:S(I)
	OUTPUT =O
END

Try it online!

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

JavaScript, 43 Bytes, assuming 1/2/2/2/...=0

for(a=prompt(b=0);a;a/=2)b+=a%2>=1;alert(b)
\$\endgroup\$
0
\$\begingroup\$

J, 32 Bytes

There's probably a more mathematical way to do this that doesn't require finding the binary representation, but I thought this was pretty good none the less:

+/@:((}:,(|~2:)@{:,<.@-:@{:)^:])

Explanation:

+/@:((}:,(|~2:)@{:,<.@-:@{:)^:])  | Full program
    (                          )  | Convert to binary list:
     (                     )^:]   | do n times:
      }:                            | Curtail the list
        ,(|~2:)@{:                  | Append the remainder mod 2 of the item dropped
                  ,<.@-:@{:       | Append the floor of half the item dropped
+/@:                                | Sum

A step by step example:

    (}:,(|~2:)@{:,<.@-:@{:) 7
1 3
^ ^
| | 
| Floor 7/2
7 % 2

    (}:,(|~2:)@{:,<.@-:@{:) 1 3
1 1 1
^ ^ ^
| | |
| | Floor 3/2
| 3 % 2
The input curtailed

    ((}:,(|~2:^#)@{:,<.@-:@{:)^:]) 7
1 1 1 0 0 0 0 0

    +/@:((}:,(|~2:)@{:,<.@-:@{:)^:]) 7
3

Of course, you would only have to do this Ceil(log2 n) times, but thats a lot harder to calculate than just n.

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

brainfuck, 34 bytes

>+<[[>-]++[>]+[<]>-]>[-<[->+<]>>]<

Try it online!

At 53 bytes, I thought the existing brainfuck solution was way too long /s. Starting cell contains the number and ends on the number of binary digits in it. Doesn't work for numbers above 255 unless you use an interpreter with larger than 8 bit or infinite cells.

How It Works

>+<[[>-]++[>]+[<]>-] Converts the number to binary
>[-<[->+<]>>]<       Adds all the numbers in the binary together
\$\endgroup\$
0
\$\begingroup\$

386 opcode, 12 Bytes

2BC0                       SUB EAX,EAX
01C9                       ADD ECX,ECX
83D000                     ADC EAX,0
41                         INC ECX
E2 F8                      LOOP $-6
EE                         OUT EDX,AL ; assuming it's a display port ...
C3                         RET
\$\endgroup\$
0
\$\begingroup\$

halen (1916 bytes)

cunt emiya fuck mh20 fuck karna dick fuck altera fuck altria tits mh20 shit karna hell piss altera tits karna shit mh20 hell piss altera piss altria cock cunt beowulf fuck emiya dick fuck altera fuck altria fuck karna fuck mh20 fuck blackbeard blackbeard tits cunt emiya fuck emiya fuck karna piss hell piss altera tits cunt emiya fuck emiya fuck mh20 piss hell piss altera tits cunt emiya fuck emiya fuck blackbeard blackbeard piss hell piss altera piss altria cock cunt vlad3 fuck mh20 dick fuck altria arse altria hell dick tits mh20 arse altria hell piss mh20 tits cunt beowulf fuck mh20 piss hell piss mh20 twat mh20 cock cock cunt raikou dick fuck altera fuck altria fuck karna fuck lancelot fuck mh20 fuck nitocris shit nitocris arse altera hell fuck emiya emiya twat karna shit karna arse cunt vlad3 fuck karna piss hell arse altria hell dick shit karna arse karna shit emiya emiya hell tits altera shit karna hell piss nitocris tits karna shit lancelot hell piss nitocris shit nitocris arse mh20 damn nitocris arse karna hell twat karna cock cock cunt nitocris nitocris fuck nitocris dick tits nitocris hell dick fuck mh20 fuck altera shit altera arse nitocris tits mh20 hell fuck altria shit altria arse nitocris shit dick altera damn mh20 cock hell shit mh20 arse cunt nitocris nitocris fuck altera piss hell fuck emiya emiya shit emiya emiya arse emiya emiya arse altria hell damn emiya emiya cock cock cunt nitocris fuck nitocris dick fuck mh20 fuck emiya emiya tits nitocris hell hell dick fuck altera shit altera arse cunt nitocris nitocris fuck nitocris piss hell cock damn emiya emiya damn mh20 cock cunt karna dick fuck mh20 shit mh20 arse cunt raikou piss hell fuck altera fuck altria fuck arthur arse mh20 hell dick shit altera arse mh20 shit dick mh20 tits arthur damn arthur cock arse altera hell shit mh20 arse mh20 tits arthur hell cock shit mh20 arse cunt nitocris fuck altera piss hell cock

\$\endgroup\$
  • \$\begingroup\$ Err wow. Somehow more offensive than brainfuck \$\endgroup\$ – Jo King Mar 18 at 10:48
0
\$\begingroup\$

><>, 20 bytes

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

Try it online!

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

dc, 14 bytes

[2~rd0<M+]dsMx

Try it online!

Input is taken from the stack, output is left on the stack. This is the same general idea as the previous dc entry (repeatedly reduce mod 2 and add remainders), but optimizing by using non-tail recursion makes a huge difference (I'd have made this a comment on that entry, but the user hasn't been active for over a year).

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

Forth (gforth), 37 bytes

: f dup 0> if 2 /mod recurse + then ;

Try it online!

Usually recursion isn't worth it when golfing Forth because it requires the if, then, (possible else), and recurse words. In this case we can do without else and we save more in stack-manipulation than we lose from recursion

Explanation

  • If n is greater than 0, get quotient and remainder of dividing n by 2.
  • Call recursively on quotient
  • Add remainder to result

Code Explanation

: f         \ start new word definition
  dup       \ duplicate top stack value
  0> if     \ if top stack value is greater than 0
    2 /mod  \ get quotient and remainder of dividing by 2 (quotient on top of stack)
    recurse \ execute current word
    +       \ add remainder to result of recursion
  then      \ end if statement
;           \ end word definition
\$\endgroup\$
0
\$\begingroup\$

MathGolf, 12 bytes

æ_╫`¡▲ÞĽ↑;î

Try it online!

This fails for input 0, due to a bug in MathGolf. I'll explain why. But I thought it was a fun solution to this problem that might not be obvious.

This method could be seen as disallowed, but I refer to wikipedia: "The bit shifts are sometimes considered bitwise operations, because they treat a value as a series of bits rather than as a numerical quantity" (emphasis mine). I have chosen to interpret this to mean that MathGolf's bitshifts are allowed, since they don't operate on a fixed number of bytes. Bit rotating in MathGolf wraps the current number of bits in the number, and rotates using the bit width of the number. Thus, if you do this enough times, any number with \$n\$ set bits will converge to \$2^n-1\$. If you then divide the result by 2 until you reach 0, the number of divisions will represent the number of ones in the original number.

The reason that this fails for 0 is that 0 is somehow turned into 1 when left-rotated. This is a bug in the implementation of the operator, rather than this program itself, and should be fixed in an upcoming update.

Explanation

æ    ▲         do-while true using 4 operators
 _             duplicate TOS
  ╫            left-rotate bits in int, list/str
   `           duplicate the top two items
    ¡          push a, b, push a != b
               This do-while loop repeats until the left-rotated
      Þ        not implemented yet
       Ä       start block of length 1
        ½      pop a : push(a//2 if int else a/2)
         ↑     while true without popping
          ;    discard TOS
           î   index of current loop (1-based)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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