# 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 ;) Feb 12, 2016 at 16:43
• The input will be a nonzero integer Does this need to be edited following your comment about zero being a potential input? Feb 13, 2016 at 1:55
– Paul
Feb 13, 2016 at 4:17
• By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity.
– Paul
Feb 13, 2016 at 4:21
• What an odd question! Feb 16, 2016 at 17:58

# 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); 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:

x=$*;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*$/].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. Feb 14, 2016 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!) Feb 14, 2016 at 11:53 # 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, 2016 at 21:54 • @Neil Very cool. That has a somewhat counter-intuitive property but I'll take it anyway. Feb 12, 2016 at 22:28 • I was trying to come up with a new JS solution and came up with f=x=>x%2?0:1+f(x/2). It is nearly identical to your answer so I'm going to refrain from posting it as a separate answer. Dec 22, 2020 at 16:40 # 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


# J, 6 bytes

1&q:@|


Explanation:

     |    absolute value
1&q:      exponent of 2 in the prime factorization


# 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 Feb 12, 2016 at 17:22
• Remove int . It's implicit, just like the return type. Feb 14, 2016 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? Feb 14, 2016 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! Feb 14, 2016 at 7:49

# APL (Dyalog Unicode), 10 bytes

⊥⍨∘~2∘⊥⍣¯1


Try it online!

Explanation:

⊥⍨∘~2∘⊥⍣¯1
2∘⊥⍣¯1   ⍝ convert the number to binary.
~         ⍝ negate it
⊥⍨           ⍝ count trailing ones in the negated number,
⍝ effectively counting trailing zeros in the number,
⍝ effectively counting how many times is the number divisible by 2.

• 100 rep to your 100th answer... nice Apr 2, 2021 at 16:01

# Java, 27 bytes

Long::numberOfTrailingZeros


Try it online!

## Explanation

The number of times a number can be divided by 2 is equal the number of 0s after the rightmost 1 in its binary representation; Java has a built-in method for finding this. Using Long instead of Integer saves 3 bytes.

# Vyxal, 2 bytes

2Ǒ


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!

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

• Try it Online! for 2 bytes because there's a built-in for that May 27, 2022 at 2:41
• Wait what? I was searching for such a builtin for so long May 27, 2022 at 14:14

# Rust, 18 bytes

i8::trailing_zeros


Attempt This Online!

It's a builtin :) Replace i8 with any other integer type and it will also work.

# 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


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? May 8, 2016 at 2:03
• @CatsAreFluffy: Haskell has a very strict type system. div is integer division, / floating point division.
– nimi
May 8, 2016 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.

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

# 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 Feb 15, 2016 at 7:44

## ES6, 22 bytes

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


Returns -1 if you pass 0.

• Ah, nice. I forgot about clz32 :P Feb 12, 2016 at 22:10

# PARI/GP, 17 bytes

n->valuation(n,2)


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