47
\$\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
    \$\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
  • 2
    \$\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

62 Answers 62

2
\$\begingroup\$

Oracle SQL 11.2, 111 bytes

WITH v(i)AS(SELECT 1 FROM DUAL UNION ALL SELECT i+1 FROM v WHERE MOD(:1/POWER(2,i),1)=0)SELECT MAX(i)-1 FROM v;

Un-golfed

WITH v(i) AS 
(
  SELECT 1 FROM DUAL 
  UNION ALL 
  SELECT i+1 FROM v WHERE MOD(:1/POWER(2,i),1)=0
)
SELECT MAX(i)-1 FROM v;
\$\endgroup\$
2
\$\begingroup\$

Javascript ES6, 39 chars

n=>n.toString(2).match(/0*$/)[0].length

Test:

[14,20,94208,7,-4].map(n=>n.toString(2).match(/0*$/)[0].length) == "1,2,12,0,2"
\$\endgroup\$
2
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 8 chars / 10 bytes

ïⓑᴙą1

Try it here (Firefox only).

Explanation

Converts input to binary, reverses it, then gets index of first 1.

\$\endgroup\$
2
\$\begingroup\$

Python, 48 chars

print len(str(bin(int(input()))).split("1")[-1])

Simply counts the number of 0s at the end of the binary number

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

Seriously, 9 bytes

,wii2=*.

Contains an unprintable (0x7F) at the end. Hexdump:

2c77 6969 323d 2a2e 7f

Try it online!

Explanation:

,wii2=*.<0x7F>
,w              get prime factorization of input (list of base, exp pairs)
  ii            flatten first (base, exp) pair so that base, exp is top of stack
    2=*         multiply exponent by 1 if base is 2 else 0
       .<0x7F>  print top item and exit
\$\endgroup\$
1
\$\begingroup\$

Javascript, 45 39 38 bytes

1 byte off thanks @manatwork.

i=>/0*$/.exec(i.toString(2))[0].length

f=
i=>/0*$/.exec(i.toString(2))[0].length

F=i=>document.body.innerHTML+='<pre>f('+i+') -> '+f(i)+'\n</pre>'

F(14)
F(20)
F(94208)

\$\endgroup\$
  • \$\begingroup\$ .exec() is 1 character shorter, just have to reverse it: /0*$/.exec(i.toString(2)). \$\endgroup\$ – manatwork Feb 12 '16 at 17:15
  • \$\begingroup\$ @manatwork. Good one, thanks! \$\endgroup\$ – removed Feb 12 '16 at 17:23
1
\$\begingroup\$

PowerShell, 36 bytes

param($a)for(;!($a%2)){$a/=2;$o++}$o

Takes input $a, then enters a for() loop. There is no setup, but the conditional means the loop ends when $a is no longer even. Inside the loop, we just divide $a by 2 and increment a counter, then output the counter.

The above correctly accounts for negative numbers (in PowerShell, the % operator follows the sign of the dividend, but any non-zero number is truthy, the ! of which is falsey).

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

Perl 6  28  27 bytes

{($_+&-$_).polymod(2 xx*)-1}
{($_+&-$_).base(2).chars-1}

Usage:

my &code = {($_+&-$_).base(2).chars-1}

say code    14; # 1
say code    20; # 2
say code 94208; # 12
say code     7; # 0
say code    -4; # 2
\$\endgroup\$
1
\$\begingroup\$

Java, 44 39 bytes

int f(int n){return n%2==0?1+f(n/2):0;}

Works for odd, zero, and negative numbers.

Golfed 5 bytes because input will not be zero.

\$\endgroup\$
  • \$\begingroup\$ FYI, this is almost exactly like mine: codegolf.stackexchange.com/a/71853/14215 \$\endgroup\$ – Geobits Feb 12 '16 at 16:45
  • \$\begingroup\$ works for zero But we don't know what to do for zero. \$\endgroup\$ – Dennis Feb 12 '16 at 16:45
  • \$\begingroup\$ @Geobits Shoot. I didn't see yours earlier! I was looking for a Java solution, but I must have skipped over it. Sorry. \$\endgroup\$ – HyperNeutrino Feb 12 '16 at 16:45
  • \$\begingroup\$ @Dennis Good point. What I mean is that it will not crash, throw errors, or go into an indefinite loop. \$\endgroup\$ – HyperNeutrino Feb 12 '16 at 16:46
  • \$\begingroup\$ Lol 44 with strikethrough looks almost exactly the same ;) \$\endgroup\$ – HyperNeutrino Feb 12 '16 at 23:07
1
\$\begingroup\$

TeaScript, 14 9 bytes

xT2)r1)i1

Ungolfed:

xT2)       // take input and convert to base 2
    r1)    // reverse the string
       i1  // get the index of '1'

You can try it here

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use v instead of r1) to reverse the string. You also don't need the x at the beginning as it's implicitly inserted \$\endgroup\$ – Downgoat Feb 14 '16 at 20:27
1
\$\begingroup\$

Mathematica, 20 bytes

#~IntegerExponent~2&

Yet another long, un-golfable built-in...

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

R, 30 bytes

sum(gmp::factorize(scan())==2)

Assumes gmp package installed

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

POSIX shell and GNU/BSD utilities, 43 30 bytes

factor ${1#-}|rs -T|grep -xc 2

We simply count the number of 2s in the output of the factor command.

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

PHP, 36 28 bytes

Used a different approach than most others. I'm checking divisibility by 2^N where I'm increasing N until it's no longer divisible by it.

for(;0==$argv[1]%2**++$b;);echo$b-1;

Run like this (-d added for aesthetics only):

php -d error_reporting=32757 -r 'for(;0==$argv[1]%2**++$b;);echo$b-1; echo"\n";' -- -65536

Implementing orlp's log algorithm would be even shorter. I don't like the requirement to create a file for PHP golfs, but this would be the shortest:

<?=log(($x=$argv[1])&-$x,2);

Edit: I found out you can actually run that without creating a file, by piping it like this:

echo '<?=log(($x=$argv[1])&-$x,2);' | php -- -65536
\$\endgroup\$
1
\$\begingroup\$

Groovy, 83 bytes

There was not a groovy answer yet, so here goes. Definitely room for improvement.

int n=args[0].toInteger();def e(int n){x=0;while(n%2==0){n/=2;x++;};print x;};e(n);

You can use it with: groovy filename.groovy "94208"

\$\endgroup\$
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\$
  • \$\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\$ – Toby Speight Feb 16 '16 at 17:17
  • \$\begingroup\$ Or even for((o=0;1<<o&~i;++o));do :;done;echo $o for 41. \$\endgroup\$ – Toby Speight Feb 16 '16 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\$
  • \$\begingroup\$ Try ~n-2and-~e(n-2) \$\endgroup\$ – CalculatorFeline May 8 '16 at 2:08
1
\$\begingroup\$

R, 56 46 40 bytes

x=scan();a=0;while(!x%%2){x=x/2;a=a+1};a

Another answer than @mnel's one without the gmp package.

Thanks to @user5957401 for saving 10 bytes

Thanks to @Frédéric for saving 6 bytes

\$\endgroup\$
  • \$\begingroup\$ you could shorten your while condition. while(!x%%2) should do the trick. \$\endgroup\$ – user5957401 Aug 8 '16 at 20:31
  • \$\begingroup\$ Since OP's asking for either a program or a function, you could golf some bytes by taking x as a scan : x=scan();a=0;... \$\endgroup\$ – Frédéric Aug 11 '16 at 11:24
1
\$\begingroup\$

Excel, 20 bytes

Works up to 2^53 (9,007,199,254,740,990)

=LOG(GCD(A1,2^53),2)

Using Binarys, a 36 byte solution that only works up to 511:

=10-FIND(2,DEC2BIN(A2)+DEC2BIN(-A2))
\$\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\$

jq, 26 characters

[while(.%2==0;./2)]|length

Sample run:

bash-4.3$ jq '[while(.%2==0;./2)]|length' <<< 94208
12

bash-4.3$ jq '[while(.%2==0;./2)]|length' <<< -4
2

On-line test:

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

PHP, 40 bytes

function e($i){return $i%2?0:e($i/2)+1;}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the syntax highlighting edit, @rink.atendant.6 \$\endgroup\$ – Nuno Pereira Feb 14 '16 at 15:10
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\$
  • \$\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\$

R, 37 bytes

f=function(n)ifelse(n%%2,0,1+f(n/2))
or
f=function(n)if(n%%2)0 else 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.

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