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

3
\$\begingroup\$

05AB1E, 4 bytes

bR1k

Try it online!

bR1k  # full program
   k  # get 0-based index of first occurrence of...
  1   # literal...
   k  # in...
      # implicit input...
b     # in binary...
 R    # reversed...
   k  # -1 if not found (this will never happen, as the only time a binary number will not contain 1 is if it is 0 which is not considered as valid input)
      # implicit output
\$\endgroup\$
4
  • \$\begingroup\$ Smart approach! :) And also works fine for negative numbers, since the minus sign is at the end after the Reverse. Here a test suite with all test cases. \$\endgroup\$ Dec 22, 2020 at 16:32
  • \$\begingroup\$ @KevinCruijssen Cool, thanks for that. I've tried before to golf down the test suite header (just for fun) by replacing " → " with … → , but for some reason interpreting as a compressed string gives â (with an unprintable, Start of Selected Area, at the end)… do you have any idea why this happens? I'm curious to know :) \$\endgroup\$
    – Makonede
    Jan 22, 2021 at 18:18
  • \$\begingroup\$ I'm just guessing here, but since is not part of the 05AB1E codepage, and is 3 bytes in UTF-8, the space plus the first two bytes of the 3-byte character are being printed, and the last byte of is simply ignored. Still not too sure why it becomes â, though.. If I just use …→ as program it simply outputs that 3-byte character as is, even though usually gives an error if not three characters are given (i.e. …a results in an error). \$\endgroup\$ Jan 22, 2021 at 19:13
  • \$\begingroup\$ @KevinCruijssen I think I know why now. Using this online tool I was able to convert to UTF-8 codepoints, giving e2 86 92. U+00E2 is â, U+0086 is Start of Selected Area, and U+0092 is Private Use Two. \$\endgroup\$
    – Makonede
    Jan 22, 2021 at 19:27
3
\$\begingroup\$

Desmos, 37 characters

Graph link: https://www.desmos.com/calculator/y5lqwruzjp

Before use, make sure c is set to 0, and that the first line contains whichever number you want to input. When running, you can either press the metronome button to automatically run the program or press the arrow button to run one iteration of the code.

    <input>
    i=ans_0
    c=0
    c->{mod(i,2^(c+1))=0:c+1,c}

How it works

  1. The <input> is the actual number being inputted. For simplicity, it is not counted for characters.
  2. ans_0 reads the 0th line (being the input), and sets i to it.
  3. c-> declares an action, which updates c to the result.
  4. Curly brackets declare a conditional statement. The results are c+1 if the condition is true, and c if not.
  5. mod() is the modulus command. It divides the first statement by the second, and gives the result.
  6. i, as mentioned, is the input.
  7. 2^(c+1) is simply 2 raised to c+1. The +1 is used to check the next value of c. An exponent is used to repeatedly divide i by 2.
  8. =0 is the condition, used to check if the remainder is equal to 0 (i is divisible).

So, the graph first takes c, and tries to update it. It raises 2 to c+1 (to check if the c can increment), then divides the input (stored with i) by the result and returns the remainder. It then checks if that remainder is equal to 0, and if so, it sets increments c by 1. Otherwise, it doesn't change c.

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 26, 2022 at 23:43
  • \$\begingroup\$ Nice, answer, but ans_0 will not paste correctly as is. You need to add a backslash before ans, so it would actually be i=\ans_0. Also, {...} doesn't paste correctly either, you will need to add backslashes in front of both brackets and in front of the mod as well. \$\endgroup\$
    – Aiden Chow
    Jul 11, 2022 at 11:03
  • \$\begingroup\$ Also 2^(c+1) will not paste correctly either. It doesn't really matter though, because it can be golfed down to 2^c2. \$\endgroup\$
    – Aiden Chow
    Jul 11, 2022 at 11:04
  • \$\begingroup\$ One last thing: In CGCC, answers are scored in bytes, not characters, though that doesn't really matter here. What I'm confused about is how are you getting 37 bytes? Could you provide the raw code without all the spaces and <input>? \$\endgroup\$
    – Aiden Chow
    Jul 11, 2022 at 11:07
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\$

R, 30 bytes

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

Assumes gmp package installed

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

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
2
\$\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\$
2
\$\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\$
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
    May 26, 2022 at 23:46
  • \$\begingroup\$ @Seggan Thanks! Found the trick a quite a while ago when I was trying to do prime factorization in Desmos. \$\endgroup\$
    – Aiden Chow
    May 27, 2022 at 0:32
2
\$\begingroup\$

K (ngn/k), 9 8 5 7 bytes

*&|~~2\

Try it online!

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

Prolog (SWI), 39 33 32 bytes

A-B:-A/\1<1,A//2-D,B is D+1;B=0.

Try it online!

-6 bytes thanks to Jo King!

-1 byte thanks to Steffan!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Combining the two clauses saves a byte: A-B:-A/\1<1,A//2-D,B is D+1;B=0. \$\endgroup\$
    – naffetS
    Dec 9, 2022 at 0:45
  • \$\begingroup\$ @Steffan oh, of course it does. I thought of that and then just didn't try it for some reason. Thanks \$\endgroup\$
    – hakr14
    Dec 9, 2022 at 1:15
2
\$\begingroup\$

C, 23 bytes

f(x){x=x&1?0:f(x/2)+1;}

Essentially just counts leading 0s recursively.

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

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

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.