55
\$\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 '16 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\$
    – trichoplax
    Feb 13 '16 at 1:55
  • 3
    \$\begingroup\$ This is called the 2-adic valuation or 2-adic order. \$\endgroup\$
    – Paul
    Feb 13 '16 at 4:17
  • 7
    \$\begingroup\$ By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity. \$\endgroup\$
    – Paul
    Feb 13 '16 at 4:21
  • 3
    \$\begingroup\$ What an odd question! \$\endgroup\$
    – corsiKa
    Feb 16 '16 at 17:58

72 Answers 72

1 2
3
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 '16 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\$

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 '20 at 7:30
0
\$\begingroup\$

Perl 5 -p, 28 bytes

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

Try it online!

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

MMIX, 12 bytes (3 instrs)

This is straight out of Knuth volume 4a.

27FF0001 DA00FF00 F8010000

Disassembly and explanation

rho SUBU $255,$0,1      // tmp = x - 1
    SADD $0,$255,$0     // x = popcnt(tmp & ~x)
    POP  1,0            // return x

No, seriously, that's it. An input of 0 gives an output of 64.

\$\endgroup\$
1 2
3

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.