61
\$\begingroup\$

The ancient Greeks had these things called singly and doubly even numbers. An example of a singly even number is 14. It can be divided by 2 once, and has at that point become an odd number (7), after which it is not divisible by 2 anymore. A doubly even number is 20. It can be divided by 2 twice, and then becomes 5.

Your task is to write a function or program that takes an integer as input, and outputs the number of times it is divisible by 2 as an integer, in as few bytes as possible. The input will be a nonzero integer (any positive or negative value, within the limits of your language).

Test cases:

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

The answer with the least bytes wins.

Tip: Try converting the number to base 2. See what that tells you.

\$\endgroup\$
11
  • 11
    \$\begingroup\$ @AlexL. You could also look at it is never becoming odd, so infinitely even. I could save a few bytes if a stack overflow is allowed ;) \$\endgroup\$
    – Geobits
    Feb 12, 2016 at 16:43
  • 1
    \$\begingroup\$ The input will be a nonzero integer Does this need to be edited following your comment about zero being a potential input? \$\endgroup\$ Feb 13, 2016 at 1:55
  • 4
    \$\begingroup\$ This is called the 2-adic valuation or 2-adic order. \$\endgroup\$
    – Paul
    Feb 13, 2016 at 4:17
  • 8
    \$\begingroup\$ By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity. \$\endgroup\$
    – Paul
    Feb 13, 2016 at 4:21
  • 3
    \$\begingroup\$ What an odd question! \$\endgroup\$
    – corsiKa
    Feb 16, 2016 at 17:58

90 Answers 90

1 2
3
1
\$\begingroup\$

Pure Bash, 40

If 0 could not be submited as input... Thanks to @TobySpeight for help me to drop a lot.

for((o=0;1<<o&~i;++o));do :;done;echo $o

Proof

pureBashStr='for((o=0;1<<o&~i;o++));do :;done;echo $o'
echo ${#pureBashStr}
40

for i in 14 20 64#w0000 94208 7 -4 ;do
    printf " %8s: %4d\n" $i $(
        eval $pureBashStr)
  done
       14:    1
       20:    2
 64#w0000:   29
    94208:   12
        7:    0
       -4:    2

+10 to support 0 case: 50

pureBashStr='for((o=0;1<<o&~i;o++));do((i))||break;done;echo $o'
i=0
printf " %8s: %4d\n" $i $(eval $pureBashStr)
        0:    0
\$\endgroup\$
2
  • \$\begingroup\$ i cannot be zero, according to the question. I think you can simplify the test to o=0;until((1<<o&i));do((++o));done;echo $o for 43 bytes. \$\endgroup\$ Feb 16, 2016 at 17:17
  • \$\begingroup\$ Or even for((o=0;1<<o&~i;++o));do :;done;echo $o for 41. \$\endgroup\$ Feb 16, 2016 at 17:29
1
\$\begingroup\$

Python 2, 27 bytes

e=lambda n:~n%2and e(n/2)+1

In Python 3, you'd have to use e(n//2), since ~ operator doesn't work with floats.

\$\endgroup\$
1
  • \$\begingroup\$ Try ~n-2and-~e(n-2) \$\endgroup\$ May 8, 2016 at 2:08
1
\$\begingroup\$

SmileBASIC, 45 bytes

INPUT N@L
IF!(N<<31)THEN N=N>>1Q=Q+!GOTO@L
?Q

I'm pretty sure N<<31 is the shortest way to check the lowest bit in SB, since ​ MOD ​ and ​ AND ​ are so long.

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

Pure bash, 37 bytes

(($1%2))&&echo 0||echo $[1+`$0 $1/2`]

A recursive solution.

\$\endgroup\$
1
  • \$\begingroup\$ @Makonede I don't see any missing parenthesis. There are two left parentheses at the beginning, two matching right parentheses after the "2", and no other parentheses in the script. Plus I tried it out again and it works. (Save it under some name and pass it one integer as a command line argument.) This is from almost 4 years ago, and I barely even recall doing it! \$\endgroup\$ Dec 21, 2020 at 7:30
1
\$\begingroup\$

BASIC, 36 bytes

while(!mod(a,2)):a=a/2:b=b+1:wend:?b

Try it online!

It's never going to win, but it's interesting to see how competitive good old fashioned BASIC can be in this sort of thing. I managed to tie with a lot of similar 36 byte solutions in trendier languages like C and Javascript, which is good enough for me.

The implementation is totally straightforward, dividing then incrementing a counter for as long as there is no remainder. I'm sure a more creative solution could reduce this byte count.

I noted that the posted solution algorithms don't account for the actual input, so I've done it as READ/DATA in the header and footer. All the test cases are there - just change the REMark so your desired test has no REM to evaluate. Or put your own "DATA whatever" line and see how my algorithm performs. 😜

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

R, 37 35 bytes

f=function(n)"if"(n%%2,0,1+f(n/2))

Checks if the current number is divisible by two. If not, returns 0, if it is, divides and recursively calls itself again while setting up a counter to add 1.

HT -- Giuseppe for replacing ifelse with "if" to lose 2 characters

\$\endgroup\$
4
  • 1
    \$\begingroup\$ This could be f=function(n)"if"(n%%2,0,1+f(n/2)) which should be 35 bytes, I think. \$\endgroup\$
    – Giuseppe
    Feb 26, 2021 at 21:33
  • \$\begingroup\$ You are correct. I don't think I understand how this works though. "rnorm"(10) will summon the rnorm function with an input of 10. But the if function doesn't work with multiple inputs, and "rno"(10) won't work to summon rnorm, so its not a straightforward look at the search path to get us from "if" to ifelse. Is there any chance you could explain? \$\endgroup\$ Feb 27, 2021 at 22:32
  • 1
    \$\begingroup\$ That code is actually applying the if function, not ifelse. if is one of R's reserved words, but it's actually a 3-argument function if(cond,cons.expr,alt.expr), and the "usual" syntax is a sugared version. Heck, for is a 3-argument function for(var,seq,expr). But wrapping a function name in quotes still lets you apply it, probably by calling match.fun under the hood. \$\endgroup\$
    – Giuseppe
    Feb 28, 2021 at 1:34
  • \$\begingroup\$ Thoroughly appreciate this explainer. Thanks. \$\endgroup\$ Feb 28, 2021 at 21:39
1
\$\begingroup\$

Templates Considered Harmful, 56 bytes

Fun<If<Rem<A<1>,I<2>>,F,Add<T,Ap<A<0>,Div<A<1>,I<2>>>>>>

Try it online!

Anonymous function that takes an int as input. If it is odd, return 0. Otherwise, add 1 and run function again with input/2.

Fun<
    If<Rem<Arg<1>,Int<2>>,
       Int<0>,
       Add<Int<1>,
           Ap<Arg<0>,
              Div<Arg<1>,Int<2>>
           >
       >
    >
>
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice answer! (and an interesting language!) \$\endgroup\$
    – user
    Mar 4, 2021 at 22:03
  • \$\begingroup\$ Thank you! I love TCH. \$\endgroup\$
    – Zack C.
    Mar 7, 2021 at 7:50
1
\$\begingroup\$

MathGolf, 4 bytes

±â1=

Bug-abuse, since it should have been 5 bytes..

Try it online.

Explanation:

±     # Get the absolute value of the (implicit) input-integer
 â    # Convert it to a reversed list of bits
  1=  # Get the 0-based index of the first 1
      # (after which the entire stack is output implicitly as result)

â should convert the integer to a binary-list, but instead converts it to a reversed binary-list, saving us the need for an explicit x to revert it.

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

Python 3.8 (pre-release), 50 bytes

lambda n: sum(1 for c in bin(n)[::-1] if c=='0')-1

Try it online!

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

JavaScript (30 bytes)

A couple of years later, and I've come across another solution after experimenting with bitwise operators. Not the shortest JS answer, but certainly pretty, if you ask me.

n=>(-n&n).toString(2).length-1
\$\endgroup\$
1
\$\begingroup\$

><>, 13 bytes

0$:2,@2%?n1+!

Try it online!

Explanation

   0           !  # initialize evenness as 0 on 1st iteration and skip on subsequent
    $:2,@         # divide a copy of the input by 2 and move to bottom of stack
         2%       # mod the 2nd copy by 2
           ?n     # print evenness if it's true (non-0)
             1+   # increment evenness for next iteration
    $             # error out after printing
\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 4 bytes

Af2c

Attempt This Online!

Explanation

Af2c  # Implicit input
A     # Get the absolute value
 f    # Push the prime factors
  2c  # Count the 2s
      # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Rockstar, 100 bytes

listen to N
X's 0
while 1
let M be N/2
turn up M
if M's N/2
build X up
let N be M
else
break


say X

Try it (Code will need to be pasted in)

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

Julia 0.6, 22 bytes

~x=length(bin(x&-x))-1

Try it online!

Port of orlp's Python answer. The function bin is deprecated in Julia 0.7 and removed in 1.0.

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

Nekomata, 2 bytes

ˡ½

Attempt This Online!

ˡ       Apply the following function repeatedly until it fails,
            and count the number of steps
 ½      Check if the input is even, and halve it
\$\endgroup\$
1
\$\begingroup\$

Pascal, 78 B

The recursive definition beats the iterative definition in length. However, the abort condition odd(x) is not guaranteed to be fulfilled for the entire domain of f. If x is 0, it is not odd and x div 2 cannot turn 0 into an odd number. Hence in production use you will prefer a while odd(x) loop (unless the domain is restricted to exclude zero).

function f(x:integer):integer;begin if odd(x)then f:=0 else f:=1+f(x div 2)end
\$\endgroup\$
0
\$\begingroup\$

Pylons, 22 bytes.

:Ai0?Aw[A2A/]1+,2A%1g}

Man, this turned out a lot longer than I thought it would.

Turns out it broke on 0 input, so I fixed it.

How it works:

:Ai     # Set A equal to command line input.
0       # Push 0 to the stack.
?A      # Check if A is equal to the top of the stack, if so, skip the next instrutction. In this case, the while loop.
w       # Start a while loop.
 [A2A/] # Set A equal to A / 2.
 1+     # Push 1 to the stack and add it to the number at the top of the stack.
 ,      # Switch to loop iteration.
 2A%    # Push A%2 to the loop condition stack.
    1g  # Check if 1 is greater than the top of the loop condition stack. 
      } # End the while loop
        # Print the stack at the end of the instruction set.
\$\endgroup\$
0
\$\begingroup\$

Whitespace, 109 bytes

Unfortunately I can't put the code here because it gets recognized as formating so this will have to do. http://pastebin.com/cmH30iUF

Try it here: http://ws2js.luilak.net/interpreter.html Just paste the code, type a number, and hit enter.

\$\endgroup\$
1
  • \$\begingroup\$ Another option is to use STL for the code here, since link-only answers are discouraged. Here's an example. \$\endgroup\$
    – Geobits
    Feb 16, 2016 at 14:47
0
\$\begingroup\$

MS SQL, 81 bytes

For funsies. convert( varbinary() ) end up taking more space than the modulo loop.

create proc p @n int as declare @i int=0while @n%2=0 select @i+=1,@n=@n/2print @i

Test with

p 14;
go
p 20;
go
p 94208;
go
p 7;
go
p -4;
go
\$\endgroup\$
0
\$\begingroup\$

dc, 21 bytes

#!/usr/bin/dc
?[dd2/r2%0=f]dsfxz2-p

Reads the input, then successively divides by 2, building a stack as we go. When we get to an odd number, count the stack depth, adjusting for the odd number and its duplicate.

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

Turing Machine, 53 char

   B    1   i

0  B4L  i1R 

1  B2L  11R 

2       B3L B7L

3           10R

4  B5L  

5  16R  

6  B0R  16R 

7  Bh   B7L 

*       1*L

It accepts as an input a string of ones and outputs a string of ones. It repeatedly divides the number by 2 and adds 1 to the count after every halving. Try it out here.

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

Scala 42 bytes

def e(n:Int):Int=if(n%2==0)e(n/2)+1 else 0

Similar to Java, but 2 bytes smaller.

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

Microscript II, 28 27 bytes

0s<N[sv2sl%!(.5*v>1+s<l)]>o

There's probably still room for improvement here.

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

Perl 5, 26 bytes

25, plus 1 for -pe instead of -e.

$i++,$_/=2until$_%2;$_=$i

or

$_=sprintf'%b',$_;s/.*1//

(The latter has output in unary.)

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

Perl 5 -p, 28 bytes

$_/=2;/\./||++$\&redo}{$\|=0

Try it online!

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

Julia 1.5.3

Not sure how to count bytes, but Julia has a built-in function for this.

help?> ?trailing_zeros
search: trailing_zeros

  trailing_zeros(x::Integer) -> Integer

  Number of zeros trailing the binary representation of x.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> trailing_zeros(2)
  1

Modifying the Python solution gives the following:

julia> f=n->length(string(n&-n,base=2))-1
#1 (generic function with 1 method)

julia> f(94208)
12
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Welcome to the site! Is it possible you could edit in an actual answer (keep in mind that builtin functions are an answer by themselves), maybe using the template provided by TryItOnline to make your actual answer clearer and to provide a testing environment for other users? \$\endgroup\$ Dec 26, 2020 at 20:35
0
\$\begingroup\$

Perl 5 + -pl060, 21 bytes

26 bytes using old rules scoring flags.

Uses the -l060 flag to preset $\ to 0, and increments it until $_/=2 is no longer even.

$_/=2,++$\until$_%2}{

Try it online!

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

Ly, 41 bytes

n0sG2*,*[:2%[lu;]pl`sp:2/r01[p`0IL]p-rpr]

Try it online!

Well, this was trickier than I expected... Division in Ly yields floating point numbers, which was a challenge for this one. Figuring out how to work around that was fun though. :)

n                                         - read the number onto the stack
 0s                                       - init accumulator to 0
   G                                      - push 1 if "n>0"
    2*,                                   - map 0->-1 and 1->0
       *                                  - effectively "n=abs(n)"
        [                               ] - infinite loop
         :2%                              - push 1|0 for "is it odd?"
            [   ]p                        - if odd...
             lu;                          - load accumulator, print and exit
                  l`sp                    - increment accumulator
                      :2/                 - calc number we want (as float)
                         r0               - init "int" result to 0 on bottom of stack 
                           1[p    ]p      - loop while to of stack is 1
                              `           - increment "int" result
                               0I         - load "float" result
                                 L        - is "int" < "float"?
                                    -     - decrement "n" by "int" result
                                     rpr  - delete bottom of stack
\$\endgroup\$
0
\$\begingroup\$

Japt, 7 bytes

v ©ÒßUz

Try it

4 bytes

Originally had this, but it's the same as ETH's solution.

¤Ôb1

Try it

Explanations

v ©ÒßUz     :Implicit input of integer U
v           :Divisible by 2? (returns 0 or 1)
  ©         :Logical AND with
   Ò        :Negate the bitwise NOT of
    ß       :Recursive call with argument
     Uz     :  U floor divided by 2

¤Ôb1     :Implicit input of integer U
¤        :Convert to binary string
 Ô       :Reverse
  b1     :First 0-based index of 1 
\$\endgroup\$
0
\$\begingroup\$

Commodore C64 BASIC, 86 83 BASIC Bytes used

This method in Commodore BASIC uses the def fn function, which is somewhat limited but can be useful. My favourite YouTube Channel 8-BIT Show and Tell talks about this and other rarely used commands in some depth here. If you are interested, it's worth mulling over.

0deffnm(a)=a-int(a/2)*2:inputx:y=-(fnm(x)=0):ify=0goto2
1x=x/2:iffnm(x)=0theny=y+1:goto1
2printy

How it works

The function that I've defined (referenced as fnm(x)) simply acts like a modulus operator in modern days computer programming languages like C and C++. In this instance, we are returning the remainder of any division by 2.

The inputx waits for a numeric input, which can be an integer or a floating point number (in fact, Commodore BASIC only really deals with floating point numbers in the ROM, but that's for another time). So note that I've not included a sanity check for floats, nor for 0, which will be an endless loop.

Once you enter a value, y=-(fnm(x)=0) is a short-hand any byte-saving way of if fn m(x) = 0 then let y = 0: end: else let y = 1. Note that like many BASIC dialects, Commodore BASIC uses a single equals for assignment and comparison. Commodore BASIC also returns -1 as true and 0 as false, as we want to initialise y with the value of 1 if the number entered is an even number, so it will divide equally by two at least once. So, now if y is 0 and the number entered is odd, then we print it and end.

In line 1, we have a loop which divides the number entered into x by 2; if that is even, then we increase the y counter by one and go back to the start of line 1 to divide x by 2 again, and so on until x is odd. On this note the loop ends and y is printed.

How even is a number? Commodore C64

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