43
\$\begingroup\$

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
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
\$\endgroup\$
  • 8
    \$\begingroup\$ OEIS A043276 \$\endgroup\$ – alephalpha Jan 13 '17 at 4:45
  • \$\begingroup\$ Can we assume any bound of the size of the integer like 32 bit or 64 bit? \$\endgroup\$ – xnor Jan 13 '17 at 5:55
  • \$\begingroup\$ @xnor yes you can assume the int is 32 bits max \$\endgroup\$ – Arnaud Jan 13 '17 at 6:20

41 Answers 41

1
\$\begingroup\$

MATL, 6 bytes

BY'X>&

Try it online!

Explanation

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
\$\endgroup\$
1
\$\begingroup\$

PHP, 82 bytes

<?=preg_match_all('!(.)\\1*!',decbin($argv[1]),$a);max(array_map('strlen',$a[0]));
\$\endgroup\$
1
\$\begingroup\$

Haskell, 74 72 bytes

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 ...

\$\endgroup\$
1
\$\begingroup\$

Retina, 50 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

Try it online!

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.

\$\endgroup\$
1
\$\begingroup\$

MATLAB, 59 bytes

@(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.

\$\endgroup\$
1
\$\begingroup\$

Japt, 28 bytes

¢q0 m@XlÃn gJ w¢q1 m@XlÃn gJ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C, 81 72 bytes

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.

\$\endgroup\$
1
\$\begingroup\$

Scala, 73 bytes

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.

\$\endgroup\$
1
\$\begingroup\$

Dyalog APL, 19 bytes

{≢⍉↑⊂⍨2≠/2,2⊥⍣¯1⊢⍵}

\$\endgroup\$
1
\$\begingroup\$

R, 38 bytes

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:

intToBits returns 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.

\$\endgroup\$
1
\$\begingroup\$

PHP, 61 68 bytes

<?=strlen(max(explode(0,strtr($s=decbin($argv[1]),10,"01")."0$s")));

takes input from command line argument.

  • convert input to binary
  • concat inverted binary + "0" + binary
  • split by 0 -> array of "11" "1111" etc.
  • get longest streak -> string of 1s
  • print string length

96 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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.