How even is a number?
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 withgcc -c evenness.s -o evenness.o
- Save the following test driver as
evenness-main.c
and compile withgcc -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
.
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.
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.