Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
11  
@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 ;) – Geobits Feb 12 at 16:43
2  
This is called the 2-adic valuation or 2-adic order. – Paul Feb 13 at 4:17
6  
By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity. – Paul Feb 13 at 4:21
2  
What an odd question! – corsiKa Feb 16 at 17:58
3  
A question with 53 answer in a week is on hold because it's unclear what you're asking ... are you kidding? – edc65 Feb 19 at 12:00

57 Answers 57

up vote 20 down vote accepted

Jelly, 4 bytes

Æfċ2

In the latest version of Jelly, ÆEḢ (3 bytes) works.

Æf      Calculate the prime factorization. On negative input, -1 appended to the end.
  ċ2    Count the 2s.

Try it here.

share|improve this answer
    
This works for negative input too. – lirtosiast Feb 12 at 16:36
1  
@ThomasKwa I don't think that counts. Maybe a meta question? – orlp Feb 12 at 16:50
    
Isn't ÆEḢ fine? It actually outputs 0 for odd numbers. – busukxuan Feb 13 at 2:08
    
@busukxuan It doesn't work for ±1. – lirtosiast Feb 13 at 2:10
1  
@Tyzoid Jelly uses its own code page on the offline interpreter by default, in which one char is one byte. – lirtosiast Feb 16 at 20:32

x86_64 machine code, 4 bytes

The BSF (bit scan forward) instruction does exactly this!

0x0f    0xbc    0xc7    0xc3

In gcc-style assembly, this is:

    .globl  f
f:
    bsfl    %edi, %eax
    ret

The input is given in the EDI register and returned in the EAX register as per standard 64-bit calling conventions.

Because of two's complement binary encoding, this works for -ve as well as +ve numbers.

Also, despite the documentation saying "If the content of the source operand is 0, the content of the destination operand is undefined.", I find on my Ubuntu VM that the output of f(0) is 0.

Instructions:

  • Save the above as evenness.s and assemble with gcc -c evenness.s -o evenness.o
  • Save the following test driver as evenness-main.c and compile with gcc -c evenness-main.c -o evenness-main.o:
#include <stdio.h>

extern int f(int n);

int main (int argc, char **argv) {
    int i;

    int testcases[] = { 14, 20, 94208, 7, 0, -4 };

    for (i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++) {
        printf("%d, %d\n", testcases[i], f(testcases[i]));
    }

    return 0;
}

Then:

  • Link: gcc evenness-main.o evenness.o -o evenness
  • Run: ./evenness

@FarazMasroor asked for more details on how this answer was derived.

I am more familiar with than the intricacies of x86 assembly, so typically I use a compiler to generate assembly code for me. I know from experience that gcc extensions such as __builtin_ffs(), __builtin_ctz() and __builtin_popcount() typically compile and assemble to 1 or 2 instructions on x86. So I started out with a function like:

int f(int n) {
    return __builtin_ctz(n);
}

Instead of using regular gcc compilation all the way to object code, you can use the -S option to compile just to assembly - gcc -S -c evenness.c. This gives an assembly file evenness.s like this:

    .file   "evenness.c"
    .text
    .globl  f
    .type   f, @function
f:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    rep bsfl    %eax, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   f, .-f
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

A lot of this can be golfed out. In particular we know that the calling convention for functions with int f(int n); signature is nice and simple - the input param is passed in the EDI register and the return value is returned in the EAX register. So we can take most of instructions out - a lot of them are concerned with saving registers and setting up a new stack frame. We don't use the stack here and only use the EAX register, so don't need to worry about other registers. This leaves "golfed" assembly code:

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Note as @zwol points out, you can also use optimized compilation to achieve a similar result. In particular -Os produces exactly the above instructions (with a few additional assembler directives that don't produce any extra object code.)

This is now assembled with gcc -c evenness.s -o evenness.o, which can then be linked into a test driver program as described above.

There are several ways to determine the machine code corresponding to this assembly. My favourite is to use the gdb disass disassembly command:

$ gdb ./evenness
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
...
Reading symbols from ./evenness...(no debugging symbols found)...done.
(gdb) disass /r f
Dump of assembler code for function f:
   0x00000000004005ae <+0>: 0f bc c7    bsf    %edi,%eax
   0x00000000004005b1 <+3>: c3  retq   
   0x00000000004005b2 <+4>: 66 2e 0f 1f 84 00 00 00 00 00   nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005bc <+14>:    0f 1f 40 00 nopl   0x0(%rax)
End of assembler dump.
(gdb) 

So we can see that the machine code for the bsf instruction is 0f bc c7 and for ret is c3.

share|improve this answer
    
Do we not count this as 2? – lirtosiast Feb 12 at 17:25
2  
How do I learn Machine Language / Byte dump code? Can't find anything online – Faraz Masroor Feb 12 at 23:17
1  
This does not satisfy the C calling convention. On x86-32, the argument is passed on the stack; on x86-64, the argument is passed in %rdi. It only appears to work within your test harness because your compiler happens to have left a stale copy of the argument in %eax. It will break if you compile the harness evenness-main.c with different optimization settings; for me it breaks with -O, -O2, or -O3. – Anders Kaseorg Feb 13 at 0:47
1  
@AndersKaseorg - thanks for pointing that out. I've restricted it just to x86_64 now, so that input comes in RDI. – Digital Trauma Feb 13 at 1:06
3  
"Also, despite the documentation saying [...]" -- Any value you get necessarily agrees with the documentation. That doesn't rule out other processor models giving a different value than yours. – hvd Feb 15 at 11:25

Python, 25 bytes

lambda n:len(bin(n&-n))-3

n & -n zeroes anything except the least significant bit, e.g. this:

100010101010100000101010000
            v
000000000000000000000010000

We are interested in the number of trailing zeroes, so we convert it to a binary string using bin, which for the above number will be "0b10000". Since we don't care about the 0b, nor the 1, we subtract 3 from that strings length.

share|improve this answer
    
after posting my answer I figured yours was very smart, so I tried to convert it to Pyth and see if yours was shorter than mine. It yielded l.&Q_Q, using log2 instead of len(bin(_)). It was the same length as my Pyth answer as well as another Pyth answer, it seems this doesn't get shorter than 6 bytes in Pyth... – busukxuan Feb 12 at 19:20

Pyth, 6 bytes

/P.aQ2

Try it here.

 P.aQ         In the prime factorization of the absolute value of the input
/    2        count the number of 2s.
share|improve this answer

JavaScript (ES6), 18 bytes

n=>Math.log2(n&-n)

4 bytes shorter than 31-Math.clz32. Hah.

share|improve this answer
1  
Oh wow, and I only recently learned about Math.clz32 too... – Neil Feb 13 at 0:06
    
Damn I was going to post exactly this! +1 – Cyoce Feb 13 at 19:25

JavaScript ES6, 22 19 bytes

f=x=>x%2?0:f(x/2)+1

Looks like recursion is the shortest route.

share|improve this answer
    
Oh nooo! You beat me! Nicely done :) +1 – Connor Bell Feb 12 at 17:03

Pyth, 8 bytes

lec.BQ\1
     Q    autoinitialized to eval(input())
   .B     convert to binary string
  c   \1  split on "1", returning an array of runs of 0s
 e        get the last run of 0s, or empty string if number ends with 1
l         take the length

For example, the binary representation of 94208 is:

10111000000000000

After splitting on 1s and taking the last element of the resulting array, this becomes:

000000000000

That's 12 zeroes, so it's "12-ly even."

This works because x / 2 is essentially x >> 1—that is, a bitshift right of 1. Therefore, a number is divisible by 2 only when the LSB is 0 (just like how a decimal number is divisible by 10 when its last digit is 0).

share|improve this answer

05AB1E, 4 5 bytes

Now supports negative numbers. Code:

Äb1¡g

Try it online!

Explanation:

Ä      # Abs(input)
 b     # Convert the number to binary
  1¡   # Split on 1's
    g  # Take the length of the last element

Uses CP-1252 encoding.

share|improve this answer

Pyth, 6 bytes

x_.BQ1

Basically just

convert2BinString(evaluatedInput())[::-1].index("1")
share|improve this answer

C, 36 (28) bytes

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

(Not testing for zero argument as a nonzero argument was specified.)

Update (in response to comment): If we allow K&R style function declarations, then we can have a 28-byte version:

f(n){return n&1?0:f(n/2)+1;}

In this case, we rely on the fact that the compiler defaults both n and the return type of f to int. This form generates a warning with C99 though and does not compile as valid C++ code.

share|improve this answer
    
If you change int n -> n it is still valid C code and cuts off 4 characters. – Josh Feb 12 at 20:43
    
Good point. I was going to say that that triggers at least a warning with C99, but so does omitting the return type. And both trigger errors in C++. So I am changing my answer appropriately. – Viktor Toth Feb 12 at 22:42

MATL, 5 bytes

Yf2=s

This works for all integers.

Try it online!

Yf      % implicit input. Compute (repeated) prime factors. For negative input
        % it computes the prime factors of the absolute value, except that for
        % -1 it produces an empty array instead of a single 1
2=s     % count occurrences of "2" in the array of prime factors
share|improve this answer
    
"And now, for something completely different..." – beaker Feb 12 at 17:52

Java 7, 39 or maybe 44 bytes

int s(int a){return a%2!=0?0:s(a/2)+1;}

int s(int a){return a%2!=0|a==0?0:s(a/2)+1;}

Yay recursion! I had to use a != instead of a shorter comparison so it wouldn't overflow on negative input, but other than that it's pretty straightforward. If it's odd, send a zero. If even, add one and do it again.

There are two versions because right now output for zero is unknown. The first will recurse until the stack overflows, and output nothing, because 0 is infinitely even. The second spits out a nice, safe, but probably-not-mathematically-rigorous 0 for output.

share|improve this answer

Perl 6, 23 18 bytes

{+($_,*/2...^*%2)}

usage

> my &f = {+($_,*/2...^*%2)}
-> ;; $_? is raw { #`(Block|117104200) ... }
> f(14)
1
> f(20)
2
> f(94208)
12
> f(7)
0
> f(-4)
2
share|improve this answer

C, 37 bytes

f(int x){return x?x&1?0:1+f(x/2):0;} Recursively check the last bit until it's not a 0.

share|improve this answer
    
Also, there is f(int n){return __builtin_ctz(n);} if you're willing to use gcc extensions. Or even #define f __builtin_ctz – Digital Trauma Feb 12 at 17:22
    
Remove int . It's implicit, just like the return type. – luser droog Feb 14 at 4:01
    
@luserdroog, You mean f(n){...}? GCC won't compile it. I'm no C expert, but a quick search reveals that maybe this feature was removed in more recent versions of C. So maybe it will compile with the appropriate flags? – Andy Soffer Feb 14 at 6:47
    
@AndySoffer I see. Maybe -ansi or -gnu99? I know I've gotten it to work. I wrote a tips answer about it! – luser droog Feb 14 at 7:49

Haskell, 28 bytes

f x|odd x=0|1<2=1+f(div x 2)

Usage example: f 94208-> 12.

If the number is odd, the result is 0, else 1 plus a recursive call with half the number.

share|improve this answer
    
div x 2? Why not x/2? – CalculatorFeline May 8 at 2:03
    
@CatsAreFluffy: Haskell has a very strict type system. div is integer division, / floating point division. – nimi May 8 at 8:19

Befunge, 20

&:2%#|_\1+\2/#
   @.<

Code execution keeps moving to the right and wrapping around to the second character of the first line (thanks to the trailing #) until 2% outputs 1, which causes _ to switch the direction to left, then | to up, which wraps around to the < on the second row, which outputs and exits. We increment the second-to-the-top element of the stack every time through the loop, then divide the top by 2.

share|improve this answer

Jolf, 6 bytes

Try it here!

Zlm)j2
Zl   2  count the number occurrences of 2 in
  m)j   the prime factorization of j (input)

Rather simple... Kudos to ETHProductions for ousting Jolf with the version that really should work!

share|improve this answer
1  
6 bytes seems to be the magic number for this challenge – Cyoce Feb 15 at 7:44

JavaScript (ES6), 20 bytes 19 bytes.

f=x=>~x%2&&1+f(x/2)

This is a port of the Haskell solution by @nimi to JavaScript. It uses the "short-circuit" properties of && which returns its left side if it is falsey (which in this case is -0) or else returns its right side. To implement odd x = 0 we therefore make the left hand side 1 - (x % 2) which bubbles 0 through the &&, otherwise we recurse to 1 + f(x / 2).

The shaving of 1 - (x % 2) as (~x) % 2 is due to @Neil below, and has the strange property that causes the above function to emit -0 for small odd numbers. This value is a peculiarity of JS's decision that integers are IEEE754 doubles; this system has a separate +0 and -0 which are special-cased in JavaScript to be === to each other. The ~ operator computes the 32-bit-signed-integer bitwise inversion for the number, which for small odd numbers will be a negative even number. (The positive number Math.pow(2, 31) + 1 for example produces 0 rather than -0.) The strange restriction to the 32-bit-signed integers does not have any other effects; in particular it does not affect correctness.

share|improve this answer
    
~x&1 is a byte shorter than 1-x%2. – Neil Feb 12 at 21:54
    
@Neil Very cool. That has a somewhat counter-intuitive property but I'll take it anyway. – CR Drost Feb 12 at 22:28

PARI/GP, 17 bytes

n->valuation(n,2)
share|improve this answer

Ruby 24 bytes

My first code golf submission (yey!)

("%b"%$*[0])[/0*$/].size

How I got here:

First I wanted to get code that actually fulfilled the spec to get my head around the problem, so I built the method without regards to number of bytes:

def how_even(x, times=1)
  half = x / 2
  if half.even?
    how_even(half, times+1)
  else
    times
  end
end

with this knowledge I de-recursed the function into a while loop and added $* (ARGV) as the input and i as the count of how many times the number has been halved before it becomes odd.

x=$*[0];i=1;while(x=x/2)%2<1;i+=1;end;i

I was quite proud of this and almost submitted it before it struck me that all this dividing by two sounded a bit binary to me, being a software engineer but not so much a computer scientist this wasn't the first thing that sprung to mind.

So I gathered some results about what the input values looked like in binary:

input      in binary      result
---------------------------------
   14               1110   1
   20              10100   2
94208  10111000000000000  12

I noticed that the result was the number of positions to the left we have to traverse before the number becomes odd.

Doing some simple string manipulations I split the string on the last occurrence of 1 and counted the length of remaining 0s:

("%b"%$*[0])[/0*$/].size

using ("%b" % x) formatting to turn a number to binary, and String#slice to slice up my string.

I have learnt a few things about ruby on this quest and look forward to more golfs soon!

share|improve this answer
1  
Welcome to Programming Puzzles and Code Golf Stack Exchange. This is a great answer; I really like the explanation. +1! If you want more code-golf challenges, click on the code-golf tag. I look forward to seeing more of your answers. – wizzwizz4 Feb 14 at 11:50
1  
Feel free to ask me about any questions you have. Type @wizzwizz4 at the beginning of a comment to reply to me. (This works with all usernames!) – wizzwizz4 Feb 14 at 11:53

J, 6 bytes

1&q:@|

Explanation:

     |    absolute value
1&q:      exponent of 2 in the prime factorization
share|improve this answer

6502 machine language, 7 bytes

To find the place value of the least significant 1 bit of the nonzero value in the accumulator, leaving the result in register X:

A2 FF E8 4A 90 FC 60

To run this on the 6502 simulator on e-tradition.net, prefix it with A9 followed by an 8-bit integer.

This disassembles to the following:

count_trailing_zeroes:
    ldx #$FF
loop:
    inx
    lsr a     ; set carry to 0 iff A divisible by 2, then divide by 2 rounding down
    bcc loop  ; keep looping if A was divisible by 2
    rts       ; return with result in X

This is equivalent to the following C, except that C requires int to be at least 16-bit:

unsigned int count_trailing_zeroes(int signed_a) {
    unsigned int carry;
    unsigned int a = signed_a;  // cast to unsigned makes shift well-defined
    unsigned int x = UINT_MAX;
    do {
        x += 1;
        carry = a & 1;
        a >>= 1;
    } while (carry == 0);
    return x;
}

The same works on a 65816, assuming MX = 01 (16-bit accumulator, 8-bit index), and is equivalent to the above C snippet.

share|improve this answer

Brachylog, 27 15 bytes

$pA:2xlL,Al-L=.

Explanation

$pA             § Unify A with the list of prime factors of the input
   :2x          § Remove all occurences of 2 in A
      lL,       § L is the length of A minus all the 2s
         Al-L=. § Unify the output with the length of A minus L
share|improve this answer

CJam, 8 bytes

rizmf2e=

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

share|improve this answer

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).

share|improve this answer
    
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") – ETHproductions Feb 12 at 16:37
    
@ETHproductions So it can! Nice catch :) – Connor Bell Feb 12 at 16:44
    
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 – ETHproductions Feb 12 at 18:04
    
Froze my computer testing this on a negative number. b%2-1 check fails for negative odd numbers. – Patrick Roberts Feb 12 at 23:23

Retina, 29 17

+`\b(1+)\1$
;$1
;

Try it online!

2 bytes saved thanks to Martin!

Takes unary input. This repeatedly matches the largest amount of 1s it can such that that number of 1s matches exactly the rest of the 1s in the number. Each time it does this it prepends a ; to the string. At the end, we count the number of ;s in the string.

If you want decimal input, add:

\d+
$0$*1

to the beginning of the program.

share|improve this answer

ES6, 22 bytes

n=>31-Math.clz32(n&-n)

Returns -1 if you pass 0.

share|improve this answer
    
Ah, nice. I forgot about clz32 :P – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 12 at 22:10

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}
share|improve this answer

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
share|improve this answer

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.

share|improve this answer
    
You might be able to take 1 byte off by replacing the costly !(n%2) with a nice little ~n&1. – John WH Smith Feb 12 at 18:24
    
@JohnWHSmith. That was nice!! Thanks – removed Feb 12 at 19:01
    
Remove the =0. Globals are implicitly initialized to 0. – luser droog Feb 14 at 3:59
    
@luserdroog. Thanks, I didn't know about that. – removed Feb 14 at 11:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.