How even is a number?

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.

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

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.

-
This works for negative input too. – lirtosiast Feb 12 at 16:36
@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
@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

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

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. - Do we not count this as 2? – lirtosiast Feb 12 at 17:25 How do I learn Machine Language / Byte dump code? Can't find anything online – Faraz Masroor Feb 12 at 23:17 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 @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 "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. - 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.  - JavaScript (ES6), 18 bytes n=>Math.log2(n&-n)  4 bytes shorter than 31-Math.clz32. Hah. - 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. - 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). - 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. - Pyth, 6 bytes x_.BQ1  Basically just convert2BinString(evaluatedInput())[::-1].index("1")  - 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. - 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  - "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. - 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

-

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.

-
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

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.

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

-

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!

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

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

-

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!

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

-

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. - Brachylog, 27 15 bytes $pA:2xlL,Al-L=.


;$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. - ES6, 22 bytes n=>31-Math.clz32(n&-n)  Returns -1 if you pass 0. - 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}

-

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

-

C, 4440 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.

-
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