# 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 '16 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 '16 at 1:55
– Paul
Feb 13 '16 at 4:17
• By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity.
– Paul
Feb 13 '16 at 4:21
• What an odd question! Feb 16 '16 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[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:

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. Feb 14 '16 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 '16 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 '16 at 21:54 • @Neil Very cool. That has a somewhat counter-intuitive property but I'll take it anyway. Feb 12 '16 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 '20 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 '16 at 17:22
• Remove int . It's implicit, just like the return type. Feb 14 '16 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 '16 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 '16 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 at 16:01

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

# 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

• 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. Dec 22 '20 at 16:32
• @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 :) Jan 22 at 18:18
• 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). Jan 22 at 19:13
• @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. Jan 22 at 19:27

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

# CJam, 8 bytes

rizmf2e=


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