Given an integer n > 0, output the length of the longest contiguous sequence of 0 or 1 in its binary representation.
Examples
6 is written 110 in binary; the longest sequence is 11, so we
should return 2 16 → 10000 → 4 893 → 1101111101 → 51337371 → 101000110100000011011 → 61 → 1 → 19965546 → 100110000000111111101010 → 7
([regex]::Matches([convert]::ToString("$args",2),'0+|1+')|% Le*|sort)[-1]
Ugh those .Net methods.
This just uses a regex to find (and match) contiguous sequences of ones and zeroes, then it takes the Length property (with a new pattern I found that uses a little known parameter set of ForEach-Object, to save 1 byte) of the resulting match objects, sorts them, and outputs the last one (the largest).
|//{y+x*y}\'~:\2\
2\ convert (implicit) input to base-2 representation~:\ build a two-item list containing the above, and the above negated{y+x*y}\' calculate "runs" of 1's, e.g. transform (0 1 1 1 0 1) into (0 1 2 3 0 1)|// return the maximum element (present in either list)
ƂĉŞ#
ƂĉŞ#
Ƃ Binary digits
ĉ Split into runs of equal digits
Ş Find the longest run
# Length
When there are multiple runs of maximum length, it will return the length multiple times. You can add the -1 flag to return it only once.
>./>#&.>((1,2~:/\[)<;.1])#:
A slightly different (and unfortunately longer) approach to miles's answer.
Usage:
>./>#&.>((1,2~:/\[)<;.1])#:893
5
Explanation
>./>#&.>((1,2~:/\[)<;.1])#:
#: Convert to base 2
( ) A fork
] Previous result
(1,2~:/\[) Find where each new sequence begins
<;.1 Cut the string of integers based on where each sequence begins and box them
#&.> Count under open - open each box and count the items in it
>./> Open all the boxes and find the maximum value
BY'X>&
B % Implicitly input a number. Convert to array of binary digits
Y' % Run length-encoding. Gives an array of values and an array of run-lengths.
% Only the latter is needed
X> % Maximum of array of run-lengths
& % Next function will use its secondary default input/output specification
% Implicitly display, only the top of the stack, as per the secondary
% default specification
<?=preg_match_all('!(.)\\1*!',decbin($argv[1]),$a);max(array_map('strlen',$a[0]));
x!0=[1]
x!n|m<-mod n 2,r<-m!div n 2=last(1:[1+r!!0|m==x]):r
maximum.(2!)
Try it online! Usage:
Prelude> maximum.(2!) $ 1337371
6
Not as nice and clean as the other Haskell answer, but some bytes shorter. The function (!) directly builds a list of lengths of 0 or 1 sequences by using a second parameter x to indicate whether a 0 or a 1 has been seen in the recursive call. If x matches the current bit, the head of the list is incremented (the sequence continues), otherwise a new 1 is appended (a new sequence with current length 1 starts). After building the list, maximum returns the maximum of the list, ie. the length of the longest sequence.
Getting rid of the x parameter by placing it as first element in the list seems not to save anything: (75 bytes)
f n|n<1=[2,1]|m<-mod n 2,x:r<-f$div n 2=m:last(1:[1+r!!0|m==x]):r
maximum.f
However maybe the maximum can be integrated in the function to save some more bytes ...
Assumes ISO 8859-1 encoding.
Half the code is just converting to binary =/
.+
$*
+`(1+)\1
${1}0
01
1
M!`0+|1+
0
1
O`1+
1+¶
1
Explanation
.+
$*
+`(1+)\1
${1}0
01
1
This converts the input number to binary.
M!`0+|1+
Splits the binary into contiguous runs of 0 and 1, separated by linefeeds.
0
1
Replace all 0s with 1s.
O`1+
Sort the runs. Since all the runs are now sequences of 1s, it will order them by length, from shortest to longest.
1+¶
Replaces all sequences of 1's followed by a linefeed with nothing. This leaves only the last (longest) sequence behind.
1
Counts the number of 1s and outputs it.
@(n)max(cellfun(@numel,regexp(dec2bin(n),'1+|0+','match')))
Uses a regexp to split into strings of 0's and 1's, then cellfun to get the number of elements in each match.
Implementing Dennis' idea, in C:
f(n){int m=0,l=0;for(n^=n<<1;n;n>>=1,l++)if(n&1)m=l>m?l:m,l=0;return m;}
Ungolfed:
f(n){
int m=0, l=0; // m: max found, l: current sequence length
n^=n<<1; // apply Dennis' XOR trick
for (; n; n>>=1,l++) // iterate each bits (shift right) until no more bits set, and inc current length
if (n&1) // if LSB bit set
m=l>m?l:m, // set m to max(m, current length)
l=0; // reset current length
return m;
}
Codepad here.
def f(a:Int,b:Int=1):Int=Math.max(b,if(a==0)0 else f(a/2,1+ ~(-a)/2%2*b))
A port of the Python 2 answer by xnor. The binary string lambda version is 2 bytes longer.
max(rev(rle(intToBits(scan()))$l)[-1])
Usage:
> max(rev(rle(intToBits(scan()))$l)[-1])
1: 6
2:
Read 1 item
[1] 2
> max(rev(rle(intToBits(scan()))$l)[-1])
1: 893
2:
Read 1 item
[1] 5
> max(rev(rle(intToBits(scan()))$l)[-1])
1: 1337371
2:
Read 1 item
[1] 6
> max(rev(rle(intToBits(scan()))$l)[-1])
1: 9965546
2:
Read 1 item
[1] 7
Ended up being a bit peculiar because of the way intToBits works.
Here is an example of how it woks with 6:
> intToBits(6)
[1] 00 01 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
[24] 00 00 00 00 00 00 00 00 00
> rle(intToBits(6))
Run Length Encoding
lengths: int [1:3] 1 2 29
values : raw [1:3] 00 01 00
> rle(intToBits(6))$l
[1] 1 2 29
> rev(rle(intToBits(6))$l)[-1]
[1] 2 1
> max(rev(rle(intToBits(6))$l)[-1])
[1] 2
From the help file for ?intToBits:
intToBitsreturns a raw vector of 32 times the length of an integer vector with entries 0 or 1. (Non-integral numeric values are truncated to integers.) [...] the unpacking is least-significant bit first.
<?=strlen(max(explode(0,strtr($s=decbin($argv[1]),10,"01")."0$s")));
takes input from command line argument.
0 -> array of "11" "1111" etc.1s96 85 bytes for arbitrary length input: coubt the bits in a loop (PHP 7.1):
for($d=2;$a=&$argv[1];$n*=$d==$b=$a[-1]%2,$d=$b,$a=bcdiv($a,2))++$n<$m?:$m=$n;echo$m;
+3 bytes for older PHP:
for($d=2;$a=&$argv[1];$n*=$d==$b=bcmod($a,2),$d=$b,$a=bcdiv($a,2))++$n<$m?:$m=$n;echo$m;
or 96 81 bytes (PHP 5.6 or later with gmplib)
for($a=gmp_init($argv[1])*$d=2;$a>>=1;$n*=$d==$a%2,$d=$a%2)$m=max($m,++$n);echo$m;
manually counting the bits in a GMP number
Standard System V ABI, signature int rfbrr(int n) (n in edi and output in eax).
31 c0 57 5e d1 ee 31 fe f3 0f bc d6 39 c2 0f 4f c2 d1 ee 75 f3 ff c0 c3
Uses @Dennis's n ^ (n >> 1) trick to reduce the problem to getting the longest string of zeros in the number plus one, then finds this by shifting through the number while it is nonzero and running tzcnt over it to count the number of trailing zeros.
rfbrr:
; clear eax
xor eax, eax
; get m in esi with (rdi->rsi >> 1) ^ (rdi)
push rdi
pop rsi ; n in esi
shr esi, 1 ; n >> 1 in esi
xor esi, edi ; m in esi
; search for longest run of zeros and return that + 1
; m is at least 1 so we dont need to do a loop check at the start
__rfbrr_lp:
; trailing zero count into edx
tzcnt edx, esi
; max of eax and edx into eax
cmp edx, eax
cmovg eax, edx
; shift m right by 1
shr esi, 1
; if m is still nonzero, loop.
jnz __rfbrr_lp
; return eax+1
inc eax
ret
GG, 20 bitsv2, 2.5 bytesbøe
GG everyone!
bøe
b # Convert number to binary.
øe # Perform run length encoding on the binary number.
# G flag takes the maximum value of the list (which is the longest run).
# Another G flag (because the run length encoding also has the digit that is part of the longest run) takes the maximum value of that list (guaranteed to be the run length).
💎
Created with the help of Luminespire.
f=(x,i=0)=>x&1?f(~x):x&&(t=f(x/2,++i))>i?t:i
f=x=>x&1?f(~x):x&&Math.max(f(x/2),Math.log2(x&-x))
Equally treat 0 and 1
