Calculate the longest series of 1's in an integer's binary value
JavaScript (ES6), 33 32 bytes
f=x=>x&(k=x>>1)?f(x&k):k&&1+f(k)
Try it online!
JavaScript (ES6), 41 40 36 34 bytes
Saved 4 bytes thanks to @ThePirateBay
f=x=>(k=x&x/2)?f(k):Math.log2(x)|0
Try it online!
How?
General case x > 0
We recursively AND the input x with x / 2 which progressively reduces the patterns of consecutive set bits until only the rightmost bit of the sequence remains. We keep a copy of the last non-zero value and determine the position of its most significant bit by floor-rounding its base-2 logarithm.
Below are the steps we go through for x = 750 (1011101110 in binary).
1011101110 --.
,----------------'
'-> 1011101110
AND 0101110111
----------
= 0001100110 --.
,----------------'
'-> 0001100110
AND 0000110011
----------
= 0000100010 --. --> output = position of MSB = 5 (0000100010)
,----------------' ^
'-> 0000100010
AND 0000010001
----------
= 0000000000
Edge case x = 0
The special case x = 0
immediately leads to Math.log2(0) | 0
. The logarithm of 0
evaluates to -Infinity
and the binary bitwise OR forces a coercion to a 32-bit integer. In compliance with the specification of the abstract operation ToInt32, this gives the expected 0
:
If number is NaN, +0, −0, +∞, or −∞, return +0
Jelly, 10 8 bytes
Ba\ÐƤṀċ¬
Try it online!
How it works
Ba\ÐƤṀċ¬ Main link. Argument: n
B Binary; convert n to base 2.
ÐƤ Apply the link to the left to all postfixes of the binary array.
a\ Cumulatively reduce by logical AND.
For example, the array
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
becomes the following array of arrays.
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 1, 1, 0]
[1, 1, 0]
[1, 0]
[0]
Ṁ Take the lexicographical maximum, i.e., the array with the most 1's at
the beginning, breaking ties by length.
¬ Yield the logical NOT of n, i.e., 0 if n > 0 and 1 if n = 0.
ċ Count the occurrences of the result to the right in the one to the left.
x86 machine code, 14 bytes
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