A bit, a nibble or byte?

Inspired by this challenge

Given an integer in the range 0 <= n < 2**64, output the minimum sized container it can fit in out of

• bit: 1
• nibble: 4
• byte: 8
• short: 16
• int: 32
• long: 64

Testcases:

0 -> 1
1 -> 1
2 -> 4
15 -> 4
16 -> 8
123 -> 8
260 -> 16
131313 -> 32
34359750709 -> 64

This is , so the shortest answer in bytes wins.

• This would be considerably easier if 2 was an output too... – ETHproductions Dec 28 '16 at 21:15
• @ETHproductions It would but alas, it isn't (it took me far to long to write an algorithm that did it) – Blue Dec 28 '16 at 21:16
• I wish I understood the problem. ... wait, all it wants is the amount of bits needed to contain the number, rounded to the next fundamental structure? – z0rberg's Dec 29 '16 at 10:48
• Thanks! I realized it when I wrote the comment and edited it too late. I guess I need a rubber duck to talk to... – z0rberg's Dec 29 '16 at 10:53
• @Daniel the answers here take a completely different approach to the other question. When I say 'inspired by' it does not mean 'duplicate of'. No answers could be trivially modified to be valid for this question – Blue Dec 29 '16 at 18:01

05AB1E, 10 bytes

bg.²îD1Q+o

Explanation

bg         Push the length of the binary representation of input without leading zeros
.²î      Push x = ceil(log2(length))
D1Q+  Add 1 if x == 1 or add 0 otherwise
o Push pow(2,x) and implicitly display it

Try it online!

Python, 39 bytes

f=lambda n:4**(n>1)*(n<16)or 2*f(n**.5)

Counts how many times one must take the square root for n to be below 16, with some special-casing to avoid outputs of 2.

If 2 were included, we could do

f=lambda n:n<2or 2*f(n**.5)

with True for 1.

41 bytes:

f=lambda n,i=1:i*(2**i>n)or f(n,i<<1+i%2)

Repeatedly doubles the exponent i until 2**i>n. Skips from i=1 to i=4 by shifting an additional bit when i is odd.

Alt 45 bytes:

f=lambda n,i=4:4**(n>1)*(2**i>n)or 2*f(n,i*2)
• It never ceases to amaze me how you can come up with so many solutions for a problem. Basically as a programmer I have learned to find a solution to a problem and work with it until it works. Guess I still have a lot to learn about golf! Respect. – ElPedro Dec 28 '16 at 22:36
• @xnor, how does your first answer output 1 when the square root of 0 or 1 is always 1 (infinite recursiveness in or 2*f(n**.5))? – dfernan Dec 29 '16 at 12:20
• @dfernan I believe the part after the or is only evaluated if the part before evaluates to something falsy (zero). For n=0, and for n=1, n>1 evaluates to False, which is treated as zero in a numeric expression, and n<16 evaluates to True, which is treated as one in a numeric expression. So 4**(n>1)*(n<16) is 1. – trichoplax Dec 29 '16 at 19:20
• @trichoplax, that is right. Thanks for the explanation. – dfernan Dec 29 '16 at 20:52

J, 19 bytes

Monadic verb taking the number on the right and spitting out the container size. There are a couple of equivalent ways of writing it so I've included both.

2^2(>.+1=>.)@^.#@#:
2^s+1=s=.2>.@^.#@#:

Explained by explosion:

2^2(>.+1=>.)@^.#@#: NB. takes one argument on the right...
#: NB. write it in binary
#@   NB. length (i.e. how many bits did that take?)
2          ^.     NB. log base 2 of that
(>.     )@       NB. ceiling
+1=>.         NB. +1 if needed (since no container is two bits wide)
2^                  NB. base 2 exponential

What's cool is we see two different ways of taking log base 2 in J. The first is the obvious 2^., which is a numerical logarithm. The second is #@#:, which can be read as "length of base-2 representation". This is almost equivalent to one-plus-floor-of-log-base-2, except that #:0 is the one-element list 0, which is exactly what we want. This beats 1+2<.@^.1&>. by 8 bytes.

In use at the REPL:

f =: 2^2(>.+1=>.)@^.#@#:
f 131313
32
f 34359750709
64
(,.f"0) 0 1 2 15 16 123 260
0  1
1  1
2  4
15  4
16  8
123  8
260 16

Old, overly clever 20 byte solution.

2&^.(>.+1=>.&.)@#@#: NB. takes one argument on the right...
#@#: NB. how many bits
2&^.                 NB. log base 2 of that
>.              NB. ceiling
+1=>.         NB. +1 if needed (since no container is two bits wide)
(       &.)      NB. undo log base 2

Python, 5350 49 bytes

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w]
• lambda n:[w for w in[1,4,8,16,32,64]if n<2**w] is one byte shorter – Blue Dec 28 '16 at 21:46
• Was just about to post something similar. +1 – ElPedro Dec 28 '16 at 21:52

Mathematica, 4439 38 bytes

Thanks @orlp for 5 bytes and @MartinEnder for 1 byte.

FirstCase[{1,4,8,16,32,64},x_/;2^x>#]&

Finds the first the elements in the list {1, 4, 8, 16, 32, 64} such that 2^number is greater than the input.

Pip, 19 bytes

(a<2**_FI2**,7RM2i)

Try it online!

How it works

a is 1st cmdline arg, i is 0 (implicit)
2**,7       Construct powers of 2 from 0 to 6 [1 2 4 8 16 32 64]
RM2    Remove 2
FI            Filter for elements for which:
a<2**_                a is less than 2 to that element
(                i)  Get 0th item of resulting list and autoprint

JavaScript (ES7), 35 bytes

n=>[1,4,8,16,32,64].find(b=>2**b>n)
• A recursive version such as f=(n,b=1)=>2**b>n&&b-2?b:f(n,b*2) should be slightly shorter. – Arnauld Dec 28 '16 at 22:47

Mathematica, 4643 38 bytes

Thanks to JungHwan Min and Martin Ender for saving 3 bytes! Thanks to ngenisis for a big 5-byte savings!

2^⌈Log2@BitLength@#⌉/.{2->4,0->1}&

Unnamed function taking a nonnegative integer as input and returning a positive integer. BitLength@# computes the number of bits in the input, and then 2^⌈Log2@...⌉ computes the smallest power of 2 that's at least as large as the number of bits. Finally, /.{2->4,0->1} takes care of the special case that there's no "niblit" between bit and nybble, and also fixes the answer for the weird input 0.

• Save 3 bytes by using BitLength@# instead of ⌊1+Log2@#⌋. Then instead of replacing with 1 you can replace 0, saving another 2 bytes and you're tied for first. – ngenisis Dec 29 '16 at 19:25
• This can actually be done entirely with BitLength. See my answer – ngenisis Dec 29 '16 at 20:12

Julia, 40 bytes

n->filter(x->n<big(2)^x,[1;2.^(2:6)])

This is an anonymous function that generates an array of the powers of 2 from 0 to 6, excluding 2, and filters it to only those elements x such that 2x is greater than the input. The first such element is the answer. Unfortunately this requires promoting 2 to a BigInt to avoid overflow on x = 64.

This is actually quite similar to orlp's Python answer, though I didn't see it before concocting this approach.

Try it online!

Perl 6, 30 bytes

{first 1+<*>$_,1,4,8,16,32,64} +< is Perl 6's left bit shift operator, which many other languages call <<. Haskell, 31 bytes f n=[2^i|i<-0:[2..],2^2^i>n]!!0 32-byte alt: f n|n<2=1|n<16=4|1>0=2*f(sqrt n) Java, 143 bytes. int f(long a){a=Long.toBinaryString(a).length();if(a<2)return 1;if(a<5)return 4;if(a<9)return 8;if(a<17)return 16;if(a<33)return 32;return 64;} • I know I can make this shorter, Io do it when I'm at a computer. – Pavel Dec 28 '16 at 22:12 • save 50 bytes: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64; – Mindwin Dec 29 '16 at 14:28 • @Mindwin I know, but I'm traveling and won't have access to a computer for a while. I'll get around to it. – Pavel Dec 29 '16 at 20:53 • Does the score make it a... love byte? – Engineer Toast Apr 3 '17 at 18:34 Haskell, 43 bytes f x=head$filter((>x).(2^))$[1,4,8,16,32,64] Ruby, 39 36 bytes ->n{2**[0,*2..6].find{|p|2**2**p>n}} Thanks G B for helping golf • Should also work without parentheses. Also, the list could be 0,2,3,4,5,6 and using 1<<2**p. – G B Dec 29 '16 at 11:16 • ... because then you could use 0,*2..6. – G B Dec 29 '16 at 12:48 Java 8, 65 55 bytes This is a lambda expression which takes a long and returns an int. Never golfed in Java before, so this should be easily beatable: x->{int i=1;while(Math.pow(2,i)<=x)i<<=1+i%2;return i;} Try it online! For 47 bytes, we could have: x->{int i=1;while(1L<<i<=x)i<<=1+i%2;return i;} However, 1L<<i overflows for return values larger than 32, so this fails for the final testcase. • This returns 4 when tested with 16 when it is supposed to return 8. Also you can still golf this solution by removing the brackets around i<<=1+i%2; since without {}s, the while loop will only execute the next line – Cows quack Dec 29 '16 at 7:44 • @KritixiLithos should be fixed now - sorry, my Java's gone rusty... – FlipTack Dec 29 '16 at 9:50 Mathematica, 30 bytes 2^(f=BitLength)[f@#-1]/. 2->4& Explanation: Let N be the set of nonnegative integers. Define two functions on N, BitLength and NextPower as follows: BitLength(n) := min {x in N : 2^x - 1 >= n} NextPower(n) := 2^(min {x in N : 2^x >= n}) This solution essentially calculates NextPower(BitLength(n)) given an integer n >= 0. For n > 0, we can see that NextPower(n) = 2^BitLength(n-1), so NextPower(BitLength(n)) = 2^BitLength(BitLength(n)-1). Now the Mathematica BitLength built-in agrees with the definition I gave for n >= 0. For n < 0, BitLength[n] == BitLength[BitNot[n]] == BitLength[-1-n], so BitLength[-1] == BitLength == 0. Thus we get the desired answer of 1 for n==0. Since we skip straight from bit to nibble, we have to replace answers of 2 with 4. • Nicely constructed! (Shame that the space is necessary.) – Greg Martin Dec 29 '16 at 21:17 bash, 49 bytes 48 bytes for((y=1;$[y==2|$1>=1<<y];$[y*=2])){ :;};echo $y or for((y=1;$[y==2|$1>=1<<y];)){ y=$[y*2];};echo $y Save in a script and pass the number to be tested as an argument. Edit: Replaced || with |, which works because the arguments are always 0 or 1. Note: This works for integers up to the largest positive integer that your version of bash can handle. If I have time, I'll modify it to work up to 2^64-1 in versions of bash that use 32-bit signed arithmetic. In the meantime, here's a 64-byte solution that works for arbitrarily large numbers (in any bash version): for((x=dc<<<2o$1n|wc -c;$[x==2||x&(x-1)];$[x++])){ :;};echo $x Stacked, 34 30 bytes @n 1 2 6|>2\^,:n 2 log>keep 0# or {!1 2 6|>2\^,:n 2 log>keep 0#} The first takes input on the TOS and leaves output on TOS; the second is a function. Try it here! Explanation @n 1 2 6|>2\^,:n 2 log>keep 0# @n set TOS to n 1 2 6|>2\^, equiv. [1, ...2 ** range(2, 6)] : duplicate it n push n 2 log log base-2 > element-wise > keep keep only truthy values 0# yield the first element Here's an example of it working on the repl: > 8 (* input *) (8) > @n 1 2 6|>2\^,:n 2 log>keep 0# (* function *) (4) > (* output *) (4) Test cases > {!1 2 6|>2\^,:n 2 log>keep 0#} @:f () > (0 1 2 15 16 123 260 131313 34359750709)$f map
((1 1 4 4 8 8 16 32 64))
>

Or, as a full program:

{!1 2 6|>2\^,:n 2 log>keep 0#} @:f

Run like this:

echo 16 | php -R 'echo(2**ceil(log(log(1+$argv,2),2))-2?:2)+2;';echo Explanation echo # Output the result of the expression ( 2** # 2 to the power ceil(log( # The ceiling of the power of 2 of bitsize log(1+$argn,2),    # Number of bits needed
2
))
- 2 ?:               # Subtract 2 (will be added back again)
2;                   # If that results in 0, result in 2 (+2=4).
) + 2                    # Add 2.

Tweaks

• Saved 3 bytes by getting rid of the $r= assignment • Saved 2 bytes by using -R to make$argn available

CJam, 18 bytes

2ri2b,2mLm]_({)}|#

Try it online!

Explanation

2                   Push 2
ri                 Read an integer from input
2b,              Get the length of its binary representation
2mLm]         Take the ceiling of the base-2 log of the length
_(       Duplicate it and decrement it
{)}|   Pop the top element, if it's 0, increment the next element
Effectively, if ceil(log2(input)) was 1, it's incremented to 2,
otherwise it stays the same.
#  Raise 2 to that power

C, 71 52 bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
• Wouldn't an input of (1<<15)+1 or more break this because of the signed behavior of long long? The type you really want is uint64_t which necessitates #include <stdint.h> which is still a loser compared to unsigned long long! Headers are the bane of golfing in c. – dmckee Dec 29 '16 at 20:30
• @dmckee I guess it could break it, but it seems to work at least on my computer. Haven't found an example which wouldn't work. I thought of using unsigned long long or uint64_t, but since it seems to work with long long I went with it. – Steadybox Dec 29 '16 at 20:51

QBIC, 27 bytes

:~a<2|_Xq]{~a<2^t|_Xt\t=t*2

Explanation

:        Get cmd line parameter N, call it 'a'
~a<2     IF 'a' is 0 or 1 (edge case)
|_Xq]    THEN quit, printing 1 ('q' is auto-initialised to 1). ']' is END-IF
{        DO - infinite loop
2^t  't' is our current number of bits, QBIC sets t=4 at the start of the program.
2^t gives the maximum number storable in t bytes.
~a<     IF the input fits within that number,
|_Xt     THEN quit printing this 't'
\t=t*2   ELSE jump to the next bracket (which are spaced a factor 2 apart, from 4 up)
DO-loop is auto-closed by QBIC.

Pyke, 13 bytes

7Zm@2-#2R^<)h

Try it here!

7Zm@          -   [set_bit(0, i) for i in range(7)] <- create powers of 2
2-        -  ^.remove(2)
#    )h - filter(^, V)
2R^    -   2 ** i
<   -  input < ^

PHP, 43 bytes

for(;1<<2**$i++<=$argn;);echo 2**$i-=$i!=2;

Run with echo <number> | php -R '<code>'.

loops $i up until 2**(2**$i) is larger than input. (Tweak: << instead of ** to eliminate parens)
After the loop, $i is one too high; so it gets a decrement before calculating the output - but not for$i==2.