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 c 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 c 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 c 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 c 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.
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 – 2016-02-12T16:43:39.333
I'm voting to close for now until clarification is added. The answers have varying outputs, and that's not helpful to the site. – Geobits – 2016-02-12T17:20:47.380
@AlexL. I guess it would best be indefinite, though I'm not a mathematician. – busukxuan – 2016-02-12T19:37:15.457
1
The input will be a nonzero integerDoes this need to be edited following your comment about zero being a potential input? – trichoplax – 2016-02-13T01:55:35.6572This is called the 2-adic valuation or 2-adic order. – Paul – 2016-02-13T04:17:00.897
7By the way, according to Wikipedia, the p-adic valuation of 0 is defined as infinity. – Paul – 2016-02-13T04:21:10.853
@Paul I call it the lowest set bit. Thanks for your info. – John Dvorak – 2016-02-13T10:44:45.373
1@Paul think it's okay if my submission evaluates its 2-adic order as
-Infinityaccording toMath.log2(0)? – Patrick Roberts – 2016-02-13T21:47:52.870This is the "find first set" or "count trailing zeroes" function, right?
– Damian Yerrick – 2016-02-14T20:52:43.5233What an odd question! – corsiKa – 2016-02-16T17:58:37.557