24
\$\begingroup\$

Your task is to, given an unsigned integer n, find the largest number which can be created by removing a single byte (8 consecutive bits) of data.


Example

Given the number 7831, we first convert it to binary (removing any leading zeroes):

1111010010111

We then find the consecutive group of 8 bits which, when removed, will yield the largest new result. In this case, there are 3 solutions, shown below

1111010010111
  ^      ^       
   ^      ^
    ^      ^

Removing this any of these yields 11111, which we then convert back to its decimal value 31 for the answer.


Test Cases

256        ->   1
999        ->   3
7831       ->   31
131585     ->   515
7854621    ->   31261
4294967295 ->   16777215 (if your language can handle 32 bit integers)

Rules

  • It is guaranteed that the bit length of n will be larger than 8.
  • Your solution should theoretically work for any bit length of n larger than 8, but in practice, needs only work for integers 255 < n < 216
  • Input/Output should be in decimal.
  • You may submit a full program or a function.
  • This is , so the shortest program (in bytes) wins!
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't understand why people put exclamation points in challenge titles! I think it might be a character limit thing! Might be just so people notice the challenge though! \$\endgroup\$ – dkudriavtsev Nov 15 '17 at 9:06
  • 1
    \$\begingroup\$ @Mendeleev It's an imperative sentence. Those are usually terminated with exclamation points. It's only correct punctuation, why does it upset you so? \$\endgroup\$ – Arthur Nov 15 '17 at 12:58
  • 1
    \$\begingroup\$ @Mendeleev People often use an exclamation mark to indicate a joke. The OP is highlighting the fact that he's making a pun. F. Scott Fitzgerald didn't like it, but in this context, it seems fine to me. If it wasn't there, you'd probably get people complaining about his spelling. \$\endgroup\$ – bornfromanegg Nov 15 '17 at 13:50
  • \$\begingroup\$ @Mendeleev because it's a bad pun... \$\endgroup\$ – FlipTack Nov 15 '17 at 15:15
  • \$\begingroup\$ @bornfromanegg I feel like people would notice the pun \$\endgroup\$ – dkudriavtsev Nov 15 '17 at 18:19

23 Answers 23

16
\$\begingroup\$

Jelly, 6 bytes

BḄ-8ƤṀ

A monadic link taking a number and returning a number.

Try it online!

How?

Uses a nice quick, Ƥ, developed by miles...

BḄ-8ƤṀ - Link: number
B      - convert to a binary list
    Ƥ  - for loop over some slices to be determined...
  -8   - this is a negative nilad, therefore: use overlapping outfixes of length 8
       -   (exactly what the specification asks us to inspect)
 Ḅ     -   convert from a binary list to an integer (vectorises)
     Ṁ - maximum
\$\endgroup\$
  • \$\begingroup\$ >_> ... Wow you beat my by 10 bytes \$\endgroup\$ – Mr. Xcoder Nov 13 '17 at 18:40
8
\$\begingroup\$

J, 12 bytes

[:>./8#.\.#:

Try it online!

          #:     to binary
     8  \.       remove consecutive groups of eight
      #.         convert each result to decimal
  >./            maximum
[:               do nothing, this lets me avoid parentheses
\$\endgroup\$
  • \$\begingroup\$ What nifty algorithm do you have in there? Could you add an explanation? \$\endgroup\$ – Mr. Xcoder Nov 13 '17 at 18:08
  • \$\begingroup\$ @Mr. Xcoder FrownyFrog converts the number to a list of binary digits ( #: ), then converts all the 8-outfixes, or the list with consecutive 8-bit infixes removed back to decimal number system ( 8#.\.) and finally takes the largest one. [: simply caps the the two previous verbs, by making >./ to be executed monadically (only with right argument) \$\endgroup\$ – Galen Ivanov Nov 13 '17 at 19:41
  • \$\begingroup\$ You taught me about outfix today, thanks for that! It’s a shame it doesn’t appear to be shorter to use under-&.; this is the perfect kind of problem for it. \$\endgroup\$ – cole Nov 13 '17 at 20:25
7
\$\begingroup\$

Python 2, 41 bytes

f=lambda n:n>>8and max(n>>8,2*f(n/2)+n%2)

Try it online!

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 54 bytes

f=(n,v=n>>8,b=1,m=0)=>b>v?m:f(n,(v^n)&b^v,b+b,v>m?v:m)
<input type=number min=256 max=2147483647 oninput=o.textContent=f(this.value)><pre id=o>

Works up to 2**31-1. Because someone asked for a bit-twiddling answer...

\$\endgroup\$
4
\$\begingroup\$

Pyth, 21 bytes

L&K.>b8eS,K+*2y/b2%b2

This is a recursive function (must be called with y, or see the link).

Try it here!

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 69 bytes

Max@Array[Drop[#&@@s,#;;#+7]~FromDigits~2&,Last[s=#~RealDigits~2]-7]&

Try it online!

This solution works for large numbers Try it online!

-3 bytes from KellyLowder

\$\endgroup\$
  • \$\begingroup\$ Save 3 more bytes: Max[c=#~RealDigits~2;Array[Drop[c[[1]],#;;#+7]~FromDigits~2&,Last@c-7]]& \$\endgroup\$ – Kelly Lowder Nov 13 '17 at 22:57
  • 1
    \$\begingroup\$ @KellyLowder nice! I golfed your solution a bit more \$\endgroup\$ – J42161217 Nov 14 '17 at 0:06
3
\$\begingroup\$

Python 3, 68 66 60 bytes

-2 bytes thanks to Mr. Xcoder!

-4 bytes thanks to ovs!

-2 bytes thanks to Erik the Outgolfer!

lambda n:max(n%2**i|n>>i+8<<i for i in range(len(bin(n))-9))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 66 bytes. n.bit_length()-8 is equivalent to len(bin(n))-10. \$\endgroup\$ – Mr. Xcoder Nov 13 '17 at 18:35
  • \$\begingroup\$ 62 bytes \$\endgroup\$ – ovs Nov 13 '17 at 21:46
  • \$\begingroup\$ 61 bytes \$\endgroup\$ – Erik the Outgolfer Nov 13 '17 at 21:54
3
\$\begingroup\$

Wolfram Language (Mathematica), 46 bytes

Floor@If[#<256,0,Max[#/256,2#0[#/2]+#~Mod~2]]&

Try it online!

This version can only handle inputs up to 2518-1, otherwise we run into Mathematica's stack size limit. (The bound may vary between Mathematica installations.) The second solution in this answer avoids that.

How it works

A recursive approach based on the following logic:

  • The maximal value should be 0 for any input less than 256, since taking a byte out of the number eats the whole number. This is our base case, which is why it's included even though the specs promise us we won't have to handle such inputs.
  • Otherwise, we take the Max of two options: eat the lowest byte (giving us the input divided by 256) or chop off the lowest bit, recurse on the remaining integer, and append the lowest bit back when we're done.

Wolfram Language (Mathematica), 55 bytes

Max@Table[Mod[#,m=2^k]+Floor[#/m/2^8]m,{k,0,Log2@#-8}]&

Try it online!

An alternate version that builds a table instead of recursion, so it works for numbers of any size that Mathematica can handle.

\$\endgroup\$
  • 2
    \$\begingroup\$ The recursion depth is exceeded for numbers bigger than 10^160 although mathematica can handle bigger numbers. But I guess OP is fine with it \$\endgroup\$ – J42161217 Nov 14 '17 at 1:14
2
\$\begingroup\$

Retina, 71 67 64 bytes

.+
$*
+`(1+)\1
$+0
01
1
.
$`_$'¶
_.{7}

A`_
O^`
1G`
+1`\B
:$`:
1

Try it online! Link only includes the faster test cases, so as not to unduly overload Dennis's server. Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

.+
$*
+`(1+)\1
$+0
01
1

Convert from decimal to binary.

.
$`_$'¶
_.{7}

A`_

Construct a list of strings obtained by deleting 8 consecutive digits in all possible ways.

O^`
1G`

Sort them in reverse order and take the first (largest).

+1`\B
:$`:
1

Convert back to decimal. (See @MartinEnder's explanation.)

\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 138 134 bytes

i->{int l=0,m=0,x;String y=i.toString(i,2);for(;l<y.length()-7;m=x>m?x:m)x=i.valueOf(y.substring(0,l)+y.substring(l+++8),2);return m;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ i.toBinaryString(i) can be i.toString(i,2). \$\endgroup\$ – Kevin Cruijssen Nov 14 '17 at 8:22
2
\$\begingroup\$

ReRegex, 294 275 bytes

Saved 19 bytes by using better 'function' definitions

I'd say this is pretty good for a Regex only language.

The base lib does allow for conversion between Unary and Decimal (Which is needed as the challenge spec explicitly states decimal), but does not support Binary; So I had to write that as part of the script adding 120 bytes to it.

#import base
b(\d*):(_*)\2_b/b1$1:$2b/b(\d*):(_+)\2b/b0$1:$2b/b(\d+):b/$1/b:b/0/B(_*):1/B$1$1_:/B(_*):0/B$1$1:/B(_*):B/$1/j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/j(\d*),\1\d{0,7}:,?(.*)/,$2,/,((_+)_+),(\2),/,$1,/,(_+),(\1_*),/,$2,/^,(_*),$/d<$1>/j,b:u<(?#input)>b:

Try it online!

By Individual Regexes.

#import base
b(\d*):(_*)\2_b/b1$1:$2b/
b(\d*):(_+)\2b/b0$1:$2b/
b(\d+):b/$1/
b:b/0/
B(_*):1/B$1$1_:/
B(_*):0/B$1$1:/
B(_*):B/$1/
j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
j(\d*),\1\d{0,7}:,?(.*)/,$2,/
,((_+)_+),(\2),/,$1,/
,(_+),(\1_*),/,$2,/
^,(_*),$/d<$1>/
j,b:u<(?#input)>b:

Steps

Firstly, we import the 'base' library, which gives two regexes. One which converts u<numbers> into unary. And one which converts d<unary_underlines> back into decimal. This is because the challenge requires IO in base10.

Then we define a handful of regexes which convert unary into binary.

b(\d*):(_*)\2_b/b1$1:$2b/
b(\d*):(_+)\2b/b0$1:$2b/
b(\d+):b/$1/
b:b/0/

The first of these, b(\d*):(_*)\2_b/b1$1:$2b/ searches for b, optionally followed by some binary digits, then a :, Then any amount of underlines, followed by the exact same amount of underlines plus one, and finally another b.

We then replace that with b1 followed by the binary digits from before, :, and just the first half of the underscores, and finally the last b.

So this checks if the unary is not divisible by two, and if so, prepends 1 to it's binary digits, then divides it minus one by two.

The second one, b(\d*):(_+)\2b/b0$1:$2b/ is almost idendical, however does not check for an extra _, meaning it only matches if it is divisible by two, and in this case prepends a 0 instead.

The third one checks if we're out of unary digits, and if so, strips away the padding to just leave the binary digits.

The last one checks if there never was any binary digits supplied, and in that case just leaves 0.

The next group of Regexes we define are to convert binary back into unary, and are slightly more simple.

B(_*):1/B$1$1_:/
B(_*):0/B$1$1:/
B(_*):B/$1/

The first of this group, B(_*):1/B$1$1_:/, much like its antithesis, detects a B, followed by any amount of Unary digits, then :1. It doesn't check for the matching B in this case, as it is only searching for one digit at a time. If this is matched, it doubles the previously matched amount of unary digits and adds one, then removes the one.

The second, B(_*):0/B$1$1:/, is almost idendical to the first, except matches a 0 rather than a 1, and does not add an additional unary digit.

The last of these, B(_*):B/$1/, checks if there are no more binary digits, and if so unwraps the unary. Unlike its antithesis, this does not need a special 0 case.

Next we define the j regexes, which act as a splitting function.

j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
j(\d*),\1\d{0,7}:,?(.*)/,$2,/

The first, j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/ does most of the heavy lifting. It searches for j, optionally followed by binary digits which are the "incrementer", then a comma followed by the incrementer then exactly 8 binary digits followed by the rest of the binary number, then a :. The first of the 8 digits is appended to the incrementer, thus incrementing it, then everything but those 8 digits from the binary input is appended after the : following a ,. So (If we were using 2 digits instead of 8) j,1001: would become j1:1001:,01 then j10:1001,01,11. Additionally, the appended array elements are wrapped in Bs, to convert them back to unary.

The other, j(\d*),\1\d{0,7}:,?(.*)/,$2,/ checks if there are less than 8 binary digits left to check after the incrementer, and if so, removes everything other than the array wrapped in ,s. Eg. ,_,___,

During and after the creation of the array we define the comparison regexes.

,((_+)_+),(\2),/,$1,/
,(_+),(\1_*),/,$2,/

The first of these, ,((_+)_+),(\2),/,$1,/ checks a comma followed by some amount of underscores, then some more, followed by a comma, then the first amount of underscores, than a comma. It then replaces it with the total amount of underscores in the first element surrounded by ,s.

The latter, ,(_+),(\1_*),/,$2,/, checks for a comma followed by some amount of underscores followed by another comma, then the same amount or more underscores, and a last comma. This will instead leave the right element.

Finally, when there is on element left thus matching ^,(_*),$, we remove the surrounding commas and convert back to decimal via d<>. Then no-more regexes can fire and the output is presented.

The input is initially placed into the template j,b:u<(?#input)>b:, which first converts the decimal input to unary, eg 5 -> j,b:_____b:, then the resulting unary to binary, j,101: Then splits the binary (which doesn't work for the example), gets the largest element, converts back to decimal, and done.

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 91 bytes

j;m;t;f(x){for(j=m=0;t=x>>j+8;m<t?m=t:j++)t=t<<j|x%(1<<j);return m;}

-23 bytes from Colera Su

Supports up to 2**31-1

Try it online!

Starts with the low 8 bits (j=0), then goes up, changing output if the number with bits [j,j+8) cut out is bigger than our current, and continuing until x has no bits above j+8

\$\endgroup\$
  • 2
    \$\begingroup\$ Store x>>j+8 and x>>j+8<<j|x%(1<<j) in a variable (parentheses removed) will reduce it to 68 bytes. \$\endgroup\$ – Colera Su Nov 15 '17 at 10:10
2
\$\begingroup\$

Jelly, 12 bytes

BJṡ8ḟ@€ƊịBḄṀ

Try it online!

Saved bytes thanks to Jonathan Allan!

\$\endgroup\$
  • \$\begingroup\$ A "filter out sublists then index into" version comes in at 13 bytes \$\endgroup\$ – Jonathan Allan Nov 13 '17 at 21:49
1
\$\begingroup\$

JavaScript (ES6), 94 91 bytes

-3 bytes thanks to Justin Mariner

f=(n,d='',c=n.toString(2).match(`(${d}).{8}(.*)`))=>c?Math.max('0b'+c[1]+c[2],f(n,d+'.')):0

Just throwing out a JavaScript string-based solution, but I'm hoping someone will post a separate bitwise-based solution so I might learn something.

My solution recursively grabs an 8-bit chunk from the string, taking the maximum value that is found.

f=(n,d='',c=n.toString(2).match(`(${d}).{8}(.*)`))=>c?Math.max('0b'+c[1]+c[2],f(n,d+'.')):0

console.log(f(256));
console.log(f(999));
console.log(f(7831));
console.log(f(131585));
console.log(f(7854621));
console.log(f(4294967295));

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

C# (.NET Core), 122+13=135 120+13=133 bytes

n=>{int m=0,i=0,t;for(var b=Convert.ToString(n,2);i<b.Length-7;m=t>m?t:m)t=Convert.ToInt32(b.Remove(i++,8),2);return m;}

Try it online!

+13 for using System;

I imagine there is a way of doing this with out using Convert. Either way, I'm sure this could be reduced.

Acknowledgements

-2 bytes thanks to Kevin Cruijssen

UnGolfed

n=>{
    int m=0,
        i=0,
        t;

    // convert n to a binary string,
    // go through removing each possible byte,
    // check if this is the biggest int so far
    for (var b=Convert.ToString(n,2); i<b.Length-7; m=t>m?t:m)
        t=Convert.ToInt32(b.Remove(i++,8),2); // remove 8 bits from position i, then convert from binary string to int

    return m;
}
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by changing the while to for and putting the var b in it: for(var b=Convert.ToString(n,2);i<b.Length-7;) \$\endgroup\$ – Kevin Cruijssen Nov 14 '17 at 8:29
  • \$\begingroup\$ And you can save 1 more byte by adding a new int variable ,t and not using Math.Max, but a manual check instead: n=>{int m=0,i=0,t;for(var b=Convert.ToString(n,2);i<b.Length-7;m=t>m?t:m)t=Convert.ToInt32(b.Remove(i++,8),2);return m;} (120 + 13 bytes) \$\endgroup\$ – Kevin Cruijssen Nov 14 '17 at 8:31
1
\$\begingroup\$

PHP, 67+1 bytes

do$r=max($r,$argn&($x=2**$i++-1)|$z=$argn>>8&~$x);while($z);echo$r;

Run as pipe with -nR or try it online.

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

Pyth, 19 bytes

eSmi.>>.<.BQd8d2a6l

Alternative answer:

eSmi.<<8.>.BQdd2a6l

Explanation:

eSmi.>>.<.BQd8d2a6lQ | Implicit Q at the end, where Q = input
  m             a6lQ | Map the over [0, 1, 2, ... , floor(log base 2 of Q) - 7]
         .BQ         |  Convert Q to binary string
       .<   d        |  Cyclically rotate left by d
      >      8       |  Get string from position 8 to end.
    .>        d      |  Cyclically rotate right by d
   i           2     |  Convert from binary string to integer
eS                   | Find the last element of sorted list (maximum value)

The other answer uses a similar approach, except that it rotates right first, and gets all bits except the last 8.

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

MATL, 23 21 bytes

Bn8-:"GB[]@8:q+(XBvX>

Try it online!

B                       % Implicitly grab input, convert to binary
 n8-:                   % Create list of 1,2,... n-8, with n the size of the binary string
     "                  % Loop over this list
      GB                % Grab the input again, convert to binary once more.
        @8:q+           % Create indices of a slice of length 8
             [](        % Index into binary string, delete the slice
                XB    % Convert the remainder from binary to integer
                  vX> % Get the maximum number so far.

Sadly, Bn8-:8:!+q&) only produces the slices to be removed, not the remainder we'd like to keep.

\$\endgroup\$
  • \$\begingroup\$ This saves a couple of bytes: Bn8-:"GB[]@8:q+(XBvX> (assign [] with ( instead of using &), and replace &: by : and addition) \$\endgroup\$ – Luis Mendo Nov 14 '17 at 14:41
  • \$\begingroup\$ @LuisMendo Thanks. I misread the docs, which said somewhere that you can only use a single index for null assignments, but for a different situation. \$\endgroup\$ – Sanchises Nov 14 '17 at 16:14
0
\$\begingroup\$

Java (OpenJDK 8), 73 bytes

n->{int m=0,i=1;for(;i<n>>7;i*=2)m=Math.max(m,n&~-i|(n>>8&-i));return m;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Octave, 81 80 bytes

@(x)max(bin2dec(dec2bin(x*(c=2.^(0:(b=nextpow2(x+1)-8))))(:,[1:b b+9:end]))'./c)

Try it online!

This is a different solution to my original attempt, saving a further 14 bytes.

The code is broken down as follows:

@(x)max(                                                                       )
        bin2dec(                                                          )'./c
                                                         (:,[1:b b+9:end])
                dec2bin(x*(                            ))
                           c=2.^(0:                   )
                                   (b=nextpow2(x+1)-8)

On the sixth line the number of groups is calculated by finding the exponent of the next power of two larger than the input (number of bits in input number), and subtracting 7 as we are removing 8 bits from each group - the resulting number is stored in b for later.

We then calculate an array of powers of two on the fifth line which is large enough for all the possible groups that can be removed. We save this in variable c for later.

On the next line up (forth line), we multiply the input by the array of powers of two (essentially bit shifting each number up), and convert the result to binary. If we take the example of 7831, this results in a 2D array containing:

000001111010010111
000011110100101110
000111101001011100
001111010010111000
011110100101110000
111101001011100000

If we then chop out the centre 8 bits, that is equivalent to removing each of the groups of 8 bits. This is done by the third line.

The resulting array is converted back to decimal on the second line. We also have to divide by c to undo the scaling that was done to each group initially.

Finally on the first line an anonymous function is declared, and the maximum value from all groups is calculated.


  • Save 1 byte by using nextpow2(x+1) rather than nnz(bin2dec(x))


Original attempt - 120 98 95 bytes

@(x)max(bin2dec(reshape(repmat(a=(d=@dec2bin)(x)',1,b=nnz(a)-7)(d(255*2.^(0:b-1))'<49),[],b)'))

Try it online!

The code is split up as follows:

@(x)max(                                                                                      )
        bin2dec(                                                                             )
                reshape(                                                              ,[],b)'
                        repmat(a=(d=@dec2bin)(x)',1,b=nnz(a)-7)(                     )
                                                                d(255*2.^(0:b-1))'<49

Basically it calculates a matrix containing the possible groups of values that can be removed, and then works out which ends up giving the largest number.

Working line by line, the fifth line calculates the groups that can be removed. For example, take 7831. This is a 13bit number, giving the groups:

1111100000000
1111000000001
1110000000011
1100000000111
1000000001111
0000000011111

The result of the fifth line is a 2D logical array which can be used for indexing.

The fourth line of the code converts the input to an array of the bits (represented as characters '0' and '1'), and then replicates it n-7 times (where n in number of bits) giving one line for each possible grouping. The group mask above is used to remove each of the possible groups.

On the third line, the result is then reshaped to undo the unwanted flattening that resulted from applying the group mask. The second line converts back to an array of resulting decimal numbers. And the first line defines the anonymous function to be the maximum value of array of possible groups.


  • Saved 22 bytes by generating the matrix of groups using maths.
  • Saved 3 bytes in conversion from binary strings to logical group mask.
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 78 + 1 (-p) = 79 bytes

map{$\=$"if($"=oct$s=~s/.{$_}\K.{8}//r)>$\}2..length($s=sprintf'0b%b',$_)-10}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 55 bytes

->n{(8../$/=~"%b"%n).map{|r|n>>8&(a=-1<<r-8)|n&~a}.max}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl, 53 bytes

(the use 5.10.1 to bring perl to lanugage level 5.10.1 is free)

Give the input number on STDIN. Will run out of memory for big numbers, but the 32-bit number in the input is not yet a problem

#!/usr/bin/perl
use 5.10.1;
$_=sprintf"%b",<>;/.{8}(?{\$F[oct"0b$`$'"]})^/;say$#F
\$\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.