x86/x86-64 machine code, 14 bytes
(TODO: 13 bytes with input in EAX, return value in EDX).
Using @Arnauld's algorithm of x &= x>>1
and taking the highest set bit position in the step before x
becomes 0
.
Callable from C/C++ with signature unsigned longest_set(unsigned edi);
in the x86-64 System V ABI. The same machine-code bytes will decode the same way in 32-bit mode, but the standard 32-bit calling conventions don't put the first arg in edi
. (Changing the input register to ecx
or edx
for Windows _fastcall
/ _vectorcall
or gcc -mregparm
could be done without breaking anything.)
address machine-code
bytes
global longest_set
1 longest_set:
2 00000000 31C0 xor eax, eax ; 0 for input = 0
3
4 .loop: ; do{
5 00000002 0FBDC7 bsr eax, edi ; eax = position of highest set bit
6 ;; bsr leaves output unmodified when input = 0 (and sets ZF)
7 ;; AMD documents this; Intel manuals say unspecified but Intel CPUs implement it
8 00000005 89F9 mov ecx, edi
9 00000007 D1E9 shr ecx, 1
10 00000009 21CF and edi, ecx
11 0000000B 75F5 jnz .loop ; } while (x &= x>>1);
12
13 0000000D C3 ret
x86's BSR
instruction (Bit Scan Reverse) is perfect for this, giving us the bit-index directly, rather than counting leading zeros. (bsr
doesn't directly produce 0 for input=0 like 32-lzcnt(x)
would, but we need bsr=31-lzcnt for non-zero inputs, so lzcnt
wouldn't even save instructions, let alone byte count. Zeroing eax before the loop works because of bsr
's semi-official behaviour of leaving the destination unmodified when the input is zero.)
This would be even shorter if we could return the MSB position of the longest run. In that case, lea ecx, [rdi+rdi]
(3 bytes) would copy + left-shift instead of mov
+ shr
(4 bytes).
See this TIO link for an asm caller that does exit(longest_set(argc-1));
Testing with a shell loop:
l=(); for ((i=0;i<1025;i++));do
./longest-set-bitrun "${l[@]}"; # number of args = $i
printf "$i %#x: $?\n" $i;
l+=($i);
done | m
0 0: 0
1 0x1: 0
2 0x2: 1
3 0x3: 0
4 0x4: 2
5 0x5: 2
6 0x6: 1
7 0x7: 0
8 0x8: 3
9 0x9: 3
10 0xa: 3
11 0xb: 0
12 0xc: 2
13 0xd: 2
14 0xe: 1
15 0xf: 0
16 0x10: 4
17 0x11: 4
18 0x12: 4
19 0x13: 0
20 0x14: 4
21 0x15: 4
...
747 0x2eb: 5
748 0x2ec: 5
749 0x2ed: 5
750 0x2ee: 5
751 0x2ef: 0
752 0x2f0: 4
753 0x2f1: 4
754 0x2f2: 4
13 bytes with a custom calling convention
We could save a byte by taking the arg in EAX and returning in EDX: then we could use cdq
(1 byte) to zero the return value in the case where input = 0 (so bsr
leaves it unmodified). The value in other cases doesn't matter, overwritten by bsr
.
So cdq
replaces xor eax, eax
, saving a byte.
We do need a 0
in a different register to (not) overwrite; in the non-zero case we can't let bsr
replace the input value with its log2. So we can't avoid the instruction entirely, and taking input + returning in EAX (like GCC regparm) would mean we'd need to start with mov edx, eax
or something to copy it somewhere else, while leaving the return value 0 for the input=0 case.
0
. That's an important test case. \$\endgroup\$