58
\$\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\$
    – trichoplax
    Feb 13, 2016 at 1:55
  • 3
    \$\begingroup\$ This is called the 2-adic valuation or 2-adic order. \$\endgroup\$
    – Paul
    Feb 13, 2016 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, 2016 at 4:21
  • 3
    \$\begingroup\$ What an odd question! \$\endgroup\$
    – corsiKa
    Feb 16, 2016 at 17:58

78 Answers 78

3
\$\begingroup\$

Vyxal, 2 bytes

Try it Online!

This one by @lyxal

2Ǒ # I'm running out of things to say for this comment line
 Ǒ # How many times is the input divisible by...
2  # 2

Vyxal, 4 bytes

Eġ∆l

Try it Online!

Ported from the Desmos answer.

Eġ∆l # 4 bytes!
E    # 2^input
 ġ   # GCD of that and the input
  ∆l # log2

Vyxal, 5 bytes

bṘȧ1ḟ

Try it Online!

Strategy from the osabie answer. Suprised that there has been no Vyxal answer for a such a popular question. Bit twiddling also gives 5 bytes.

bṘȧ1ḟ # This comment line needs some love
b     # Convert to binary
 Ṙ    # Reverse
  ȧ   # Absolute value of each element in the list. This is to handle negative numbers correctly
   1ḟ # First index of 1
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Try it Online! for 2 bytes because there's a built-in for that \$\endgroup\$
    – lyxal
    yesterday
  • \$\begingroup\$ Wait what? I was searching for such a builtin for so long \$\endgroup\$
    – Seggan
    15 hours ago
2
\$\begingroup\$

CJam, 8 bytes

rizmf2e=

Read integer, absolute value, prime factorize, count twos.

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

JavaScript ES6, 36 38 bytes

Golfed two bytes thanks to @ETHproductions

Fairly boring answer, but it does the job. May actually be too similar to another answer, if he adds the suggested changes then I will remove mine.

b=>{for(c=0;b%2-1;c++)b/=2;alert(c)}

To run, assign it to a variable (a=>{for...) as it's an anonymous function, then call it with a(100).

\$\endgroup\$
4
  • \$\begingroup\$ Nice answer! b%2==0 can be changed to b%2-1, and c++ can be moved inside the last part of the for statement. I think this would also work: b=>eval("for(c=0;b%2-1;b/=2)++c") \$\endgroup\$ Feb 12, 2016 at 16:37
  • \$\begingroup\$ @ETHproductions So it can! Nice catch :) \$\endgroup\$ Feb 12, 2016 at 16:44
  • \$\begingroup\$ One more byte: b%2-1 => ~b&1 Also, I think this fails on input of 0, which can be fixed with b&&~b&1 \$\endgroup\$ Feb 12, 2016 at 18:04
  • \$\begingroup\$ Froze my computer testing this on a negative number. b%2-1 check fails for negative odd numbers. \$\endgroup\$ Feb 12, 2016 at 23:23
2
\$\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\$
2
\$\begingroup\$

DUP, 20 bytes

[$2/%0=[2/f;!1+.][0]?]f:

Try it here!

Converted to recursion, output is now the top number on stack. Usage:

94208[2/\0=[f;!1+][0]?]f:f;!

Explanation

[                ]f: {save lambda to f}
 2/\0=               {top of stack /2, check if remainder is 0}
      [     ][ ]?    {conditional}
       f;!1+         {if so, then do f(top of stack)+1}
              0      {otherwise, push 0}
\$\endgroup\$
2
\$\begingroup\$

Japt, 9 5 bytes

¢w b1

Test it online!

The previous version should have been five bytes, but this one actually works.

How it works

       // Implicit: U = input integer
¢      // Take the binary representation of U.
w      // Reverse.
b1     // Find the first index of a "1" in this string.
       // Implicit output
\$\endgroup\$
0
2
\$\begingroup\$

C, 44 40 38 36 bytes

2 bytes off thanks @JohnWHSmith. 2 bytes off thanks @luserdroog.

a;f(n){for(;~n&1;n/=2)a++;return a;}

Test live on ideone.

\$\endgroup\$
5
  • \$\begingroup\$ You might be able to take 1 byte off by replacing the costly !(n%2) with a nice little ~n&1. \$\endgroup\$ Feb 12, 2016 at 18:24
  • \$\begingroup\$ @JohnWHSmith. That was nice!! Thanks \$\endgroup\$
    – removed
    Feb 12, 2016 at 19:01
  • \$\begingroup\$ Remove the =0. Globals are implicitly initialized to 0. \$\endgroup\$ Feb 14, 2016 at 3:59
  • \$\begingroup\$ @luserdroog. Thanks, I didn't know about that. \$\endgroup\$
    – removed
    Feb 14, 2016 at 11:01
  • \$\begingroup\$ Correct me if I'm wrong but since this function uses the global variable a, isn't it only guaranteed to work the first time it's called? I didn't know that was allowed. \$\endgroup\$ Oct 27, 2016 at 1:45
2
\$\begingroup\$

Mathematica, 20 bytes

#~IntegerExponent~2&

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

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

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\$
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\$
2
\$\begingroup\$

K (ngn/k), 9 8 5 bytes

*&|2\

Try it online!

  • |2\x convert x to base 2, reversing the resulting digits
  • & use monadic where, e.g. convert 0 0 2 into 2 2
  • * return the first value
\$\endgroup\$
2
\$\begingroup\$

Desmos, 22 bytes

f(n)=log_2(gcd(n,2^n))

Try It On Desmos!

Doesn't work for 94208 because it's too large for the program. Below is one that supports much more numbers:

43 bytes

f(n)=log_2(gcd(n,2^{floor(log_2(abs(n)))}))

Try It On Desmos!

\$\endgroup\$
2
  • \$\begingroup\$ Wow this is some insight you got there \$\endgroup\$
    – Seggan
    yesterday
  • \$\begingroup\$ @Seggan Thanks! Found the trick a quite a while ago when I was trying to do prime factorization in Desmos. \$\endgroup\$
    – Aiden Chow
    yesterday
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\$
2
  • \$\begingroup\$ .exec() is 1 character shorter, just have to reverse it: /0*$/.exec(i.toString(2)). \$\endgroup\$
    – manatwork
    Feb 12, 2016 at 17:15
  • \$\begingroup\$ @manatwork. Good one, thanks! \$\endgroup\$
    – removed
    Feb 12, 2016 at 17:23
1
\$\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\$
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\$
5
  • \$\begingroup\$ FYI, this is almost exactly like mine: codegolf.stackexchange.com/a/71853/14215 \$\endgroup\$
    – Geobits
    Feb 12, 2016 at 16:45
  • \$\begingroup\$ works for zero But we don't know what to do for zero. \$\endgroup\$
    – Dennis
    Feb 12, 2016 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\$
    – hyper-neutrino
    Feb 12, 2016 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\$
    – hyper-neutrino
    Feb 12, 2016 at 16:46
  • \$\begingroup\$ Lol 44 with strikethrough looks almost exactly the same ;) \$\endgroup\$
    – hyper-neutrino
    Feb 12, 2016 at 23:07
1
\$\begingroup\$

PHP, 40 bytes

function e($i){return $i%2?0:e($i/2)+1;}
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the syntax highlighting edit, @rink.atendant.6 \$\endgroup\$ Feb 14, 2016 at 15:10
  • \$\begingroup\$ One more byte can be saved: the space between return and $i. \$\endgroup\$
    – axiac
    Dec 22, 2020 at 16:17
  • \$\begingroup\$ I think this solution should be re-labelled as PHP 7.3. PHP 7.4 introduced arrow functions that allow a much shorter solution. \$\endgroup\$
    – axiac
    Dec 22, 2020 at 16:19
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\$

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

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\$
2
  • \$\begingroup\$ you could shorten your while condition. while(!x%%2) should do the trick. \$\endgroup\$ Aug 8, 2016 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, 2016 at 11:24
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\$

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

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.