Bit run rundown

Question

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 → 5
• 1337371 → 101000110100000011011 → 6
• 1 → 1 → 1
• 9965546 → 100110000000111111101010 → 7

Answer 1

Python 2, 46 45 bytes

f=lambda n,k=1:`k`in bin(n^n/2)and-~f(n,k*10)

Try it online!

How it works

By XORing n and n/2 (dividing by 2 essentially chops off the last bit), we get a new integer m whose unset bits indicate matching adjacent bits in n.

For example, if n = 1337371, we have the following.

n    = 1337371 = 101000110100000011011₂
n/2  =  668685 =  10100011010000001101₂
m    = 1989654 = 111100101110000010110₂

This reduces the task to find the longest run of zeroes. Since the binary representation of a positive integer always begins with a 1, we'll try to find the longest 10* string of digits that appears in the binary representation of m. This can be done recursively.

Initialize k as 1. Every time f is executed, we first test if the decimal representation of k appears in the binary representation of m. If it does, we multiply k by 10 and call f again. If it doesn't, the code to the right of and isn't executed and we return False.

To do this, we first compute bin(k)[3:]. In our example, bin(k) returns '0b111100101110000010110', and the 0b1 at the beginning is removed with [3:].

Now, the -~ before the recursive call increments False/0 once for every time f is called recursively. Once 10{j} (1 followed by j repetitions of 0) does not appear in the binary representation of k, the longest run of zeroes in k has length j - 1. Since j - 1 consecutive zeroes in k indicate j matching adjacent bits in n, the desired result is j, which is what we obtain by incrementing False/0 a total of j times.

Answer 2

Python 2, 46 bytes

f=lambda n,r=1:max(r,n and f(n/2,1+~-n/2%2*r))

Try it online

Extracts binary digits from n in reverse by repeatedly taking n/2 and n%2. Tracks the length of the current run r of equal digits by resetting it to 0 if the last two digits are unequal, then adding 1.

The expression ~-n/2%2 is an indicator of whether the last two digits are equal, i.e. n is 0 or 3 modulo 4. Checking the last two digits together turned out shorten than remembering the previous digit.

Answer 3

05AB1E, 6 bytes

b.¡€gM

Try it online!

Explanation

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max

Answer 4

Mathematica, 38 bytes

Max[Length/@Split[#~IntegerDigits~2]]&

or

Max[Tr/@(1^Split[#~IntegerDigits~2])]&

Answer 5

Python, 53 bytes

import re;lambda g:max(map(len,re.findall('1+|0+',bin(g))))

Anonymous lambda function.

Answer 6

Jelly, 6 bytes

BŒgL€Ṁ

Try it online!

How it works

BŒgL€Ṁ  Main link. Argument: n

B       Binary; convert n to base 2.
 Œg     Group adjacent, identical elements.
   L€   Map length over the groups.
     Ṁ  Take the maximum.

Answer 7

Ruby, 41 40 bytes

->b{("%b%b"%[b,~b]).scan(/1+/).max.size}

Find longest sequence of '1' in b or its inverse.

Thanks to manatwork for saving 1 byte.

Answer 8

Ruby, 51 44 43 bytes

Function solution.

@manatwork is made of magic

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}

Answer 9

JavaScript (ES6), 54 bytes

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

A recursive solution with a lot of bit manipulation. n stores the input, r stores the length of the current run, l stores the length of the longest run, and d stores the previous digit.

Test snippet

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

for(var i of [0,1,2,3,4,5,6,7,8,9,16,893,1337371]) console.log(`f(${i}): ${f(i)}`)

Answer 10

Python 2, 57 bytes

a=lambda n:n and max((n&-n|~n&-~n).bit_length()-1,a(n/2))

A recursive solution. There might be a shorter form for the bit magic.

Answer 11

Perl, 43 bytes

#!perl -p
\@a[$a+=$_-1+($_>>=1)&1||-$a]while$_;$_=@a

Counting the shebang as one, input is taken from stdin.

Try it online!

Answer 12

Pip, 16 bytes

Seems like there's gotta be a shorter way to get the runs of same digit...

MX#*(TBa`1+|0+`)

Takes input as command-line argument. Try it online!

Explanation

     TBa          1st cmdline arg, To Binary
    (   `1+|0+`)  Find all matches of this regex
  #*              Map length operator to that list
MX                Get the maximum and autoprint it

Answer 13

Perl 6, 36 bytes

{(.base(2)~~m:g/1+|0+/)».chars.max}

Explanation:

{                                 }   # a lambda
  .base(2)                            # convert the argument to base 2
          ~~m:g/     /                # regex match, with global matching turned on
                1+|0+                 # match one or more 1, or one or more 0
 (                    )».chars        # replace each match by its length
                              .max    # take the maximum number

Try it online.

Answer 14

Haskell, 79 characters

maximum.map length.group.i

where

import Data.List
i 0=[]
i n=mod n 2:i(div n 2)

Or in ungolfed version:

import Data.List
pcg :: Int -> Int
pcg = maximum . map length . group . intToBin

intToBin :: Int -> [Int]
intToBin 0 = []
intToBin n = n `mod` 2 : intToBin (n `div` 2)

Explanation:

intToBin converts an int to a list of binary digits (lsb first). group groups contiguous sequences, such that [1, 1, 0, 0, 0, 1] becomes [[1, 1],[0, 0, 0],[1]]. maximum . map length calculates for each inner list its length and returns the length of the longest.

Edit: Thanks to @xnor and @Laikoni for saving bytes

Answer 15

Pyth, 7 bytes

heSr8.B

Do run length encode on the binary string, then sort it so that the longest runs come last, then take the first element (the length) of the last element (the longest run) of the list.

In pseudocode:

'  S     ' sorted(
'   r8   '   run_length_encode(
'     .BQ'     bin(input()) ))  \
'he      '   [-1][0]

Answer 16

J, 21 bytes

[:>./#:#;.1~1,2~:/\#:

Try it online!

Explanation

[:>./#:#;.1~1,2~:/\#:  Input: integer n
                   #:  Binary digits of n
              2   \    For each continuous subarray of 2 digits
               ~:/       Reduce it using not-equals
            1,         Prepend a 1 to those results
     #:                Binary digits of n
        ;.1~           Cut the binary digits at each location with a 1
       #                 Get the length of each cut
[:>./                  Reduce those lengths using maximum and return

Answer 17

Octave, 31 bytes

@(n)max(runlength(+dec2bin(n)))

Try it online!

Explanation

This is a translation of my MATL answer. My initial plan was a different approach, namely @(n)max(diff(find(diff([0 +dec2bin(n) 0])))). But it turns out that Octave has a runlength function (which I just found out about). By default it outputs only the array of run-lengths, so the desired result is the max of that array. The output of dec2bin, which is a char array (string) containing '0' and '1', needs to be converted to a numeric array using +, because runlength expects numeric input.

Answer 18

MATLAB 71 bytes

m=1;a=diff(int8(dec2bin(a)));while(any(a==0)),m=m+1;a=diff(a);end;m

This converts integer variable 'a' to a binary int8 array then counts the number of times the result has to be differentiated until there is no zero in the result.

I am new here. Is this sort of input and one-liner allowed by the PCG rules?

Answer 19

Bash / Unix utilities, 66 65 42 bytes

Thanks to @DigitalTrauma for significant improvements (23 bytes!).

dc<<<`dc -e2o?p|fold -1|uniq -c|sort -n`rp

Try it online!

Answer 20

Bash (+coreutils, +GNU grep), 33, 32 bytes

EDITS:

• Minus 1 byte (removed quotes around grep expression)

Golfed

dc -e2o$1p|grep -Po 1+\|0+|wc -L

Explained

 #Convert to binary
 >dc -e2o893p
 1101111101

 #Place each continuous run of 1es or 0es on its own line
 >dc -e2o893p|grep -Po '1+|0+'
 11
 0
 11111
 0
 1

 #Output the length of the longest line
 >dc -e2o893p|grep -Po '1+|0+'|wc -L
 5

Try It Online!

Answer 21

Brachylog, 9 bytes

$b@b:lotl

Try it online!

Explanation

$b          List of binary digits of the input
  @b        Runs of consecutive identical digits in that list
    :lo     Order those runs by length
       tl   Output is the length of the last one

Answer 22

Javascript, 66 Bytes

x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.leng‌​th))

Thanks to manatwork for the code.

Explanation

x.toString(2)

Convert number to binary string.

split(/(0+|1+)/g)

Split every different character (0 or 1) (this regex captures empty spaces but they can be ignored)

map(y=>y.length)

For each element of the array get its length and put it in the returned array.

...

Convert array to list of arguments ([1,2,3] -> 1,2,3)

Math.max()

Get the largest number out of the arguments.

Answer 23

R, 45 34 bytes

max(rle(miscFuncs::bin(scan()))$l)

Fixed a silly misunderstanding thanks to @rturnbull and @plannapus.

Answer 24

C#, 106 bytes

n=>{int l=1,o=0,p=0;foreach(var c in System.Convert.ToString(n,2)){o=c!=p?1:o+1;l=o>l?o:l;p=c;}return l;};

Formatted version:

System.Func<int, int> f = n =>
{
    int l = 1, o = 0, p = 0;
    foreach (var c in System.Convert.ToString(n, 2))
    {
        o = c != p ? 1 : o + 1;

        l = o > l ? o : l;

        p = c;
    }

    return l;
};

And an alternative approach accessing the string by index at 118 bytes, with whitespace removed:

System.Func<int, int> f2 = n =>
{
    var s = System.Convert.ToString(n, 2);

    int l = 1, c = 1, i = 0;

    for (; i < s.Length - 1; )
    {
        c = s[i] == s[++i] ? c + 1 : 1;
        l = l < c ? c : l;
    }

    return l;
};

Answer 25

Wonder, 27 bytes

max.map#len.mstr`0+|1+`g.bn

Usage:

(max.map#len.mstr`0+|1+`g.bn)123

Converts to binary, matches each sequence of 0's and 1's, gets the length of each match, and gets the maximum.

Answer 26

Batch, 102 bytes

@set/a"n=%1/2,d=%1%%2,r=1+(%3+0)*!(0%2^d),l=%4-(%4-r>>5)
@if not %n%==0 %0 %n% %d% %r% %l%
@echo %l%

Port of @edc65's answer. %2..%4 will be empty on the first call, so I have to write the expressions in such a way that they will still work. The most general case is %3 which I had to write as (%3+0). %2 is easier, as it can only be 0 or 1, which are the same in octal, so 0%2 works here. %4 turned out to be even easier, as I only need to subtract from it. (%4-r>>5) is used to compare l with r as Batch's set/a doesn't have a comparison operator.

Answer 27

PowerShell, 78 74 73 bytes

([regex]::Matches([convert]::ToString("$args",2),'0+|1+')|% Le*|sort)[-1]

Try it online!

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

Answer 28

Dyalog APL, 22 bytes

Anonymous function train

⌈/∘(≢¨⊢⊂⍨1,2≠/⊢)2⊥⍣¯1⊢

⌈/∘(... The maximum of the results of the following anonymous function-train...

 ≢¨  the tally of each

 ⊢⊂⍨ partition of the argument, where the partitioning is determined by the ones in

 1, one prepended to

 2≠/ the pairwise unequal of

 ⊢ the argument

) applied to

2⊥⍣¯1 from-base-2 applied negative one times (i.e. to-base-2, once) to

⊢ the argument

TryAPL online!

Answer 29

Japt, 15 bytes

2o!q¢ c ml n gJ

Test it online! or Verify all test cases at once.

How it works

                 // Implicit: U = input integer, J = -1
2o               // Create the range [0...2), or [0,1].
  ! ¢            // Map each item Z in this range to U.s(2)
   q             //                                        .q(Z).
                 // This returns the runs of 1's and 0's in the binary
                 // representation of U, respectively.
      c          // Flatten into a single list.
        ml       // Map each item Z to Z.length.
           n gJ  // Sort the result and grab the item at index -1, or the last item.
                 // This returns the largest element in the list.
                 // Implicit: output result of last expression

Answer 30

J, 27 bytes

>./>#&.>((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

Answer 31

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

Answer 32

PHP, 82 bytes

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

Answer 33

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

Answer 34

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.

Answer 35

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.

Answer 36

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.

Answer 37

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

Answer 38

Japt, 28 bytes

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

Try it online!

Answer 39

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.

Answer 40

Dyalog APL, 19 bytes

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

Answer 41

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.