A bit, a nibble or byte?

Question

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 code-golf, so the shortest answer in bytes wins.

Answer 1

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!

Answer 2

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)

Answer 3

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

Answer 4

Python, 53 50 49 bytes

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]

Answer 5

Mathematica, 44 39 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.

Answer 6

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

Answer 7

JavaScript (ES7), 35 bytes

n=>[1,4,8,16,32,64].find(b=>2**b>n)

Answer 8

Mathematica, 46 43 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.

Answer 9

Julia, 40 bytes

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

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 2^x 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!

Answer 10

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

Answer 11

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)

Answer 12

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;}

Answer 13

Haskell, 43 bytes

f x=head$filter((>x).(2^))$[1,4,8,16,32,64]

Answer 14

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.

Answer 15

Ruby, 39 36 bytes

->n{2**[0,*2..6].find{|p|2**2**p>n}}

Thanks G B for helping golf

Answer 16

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

Answer 17

Racket 45 bytes

(findf(λ(x)(>(expt 2 x)m))'(1 4 8 16 32 64))

Ungolfed:

(define (f m)
  (findf (λ (x) (> (expt 2 x) m))          ; find first function
         '(1 4 8 16 32 64)))

Other versions:

(define (f1 m)
  (for/last ((i '(1 4 8 16 32 64))         ; using for loop, taking last item
             #:final (> (expt 2 i) m))     ; no further loops if this is true
    i))

and using string length:

(define (f2 m)
  (for/last
      ((i '(1 4 8 16 32 64))
       #:final (<= (string-length
                    (number->string m 2))  ; convert number to binary string
                   i))
    i))

Testing:

(f 0)
(f 1)
(f 2)
(f 15)
(f 16)
(f 123)
(f 260)
(f 131313)
(f 34359750709)

Output:

1
1
4
4
8
8
16
32
64

Answer 18

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

Answer 19

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

(0 1 2 15 16 123 260 131313 34359750709) $f map

out

Answer 20

PHP, 49 46 44 bytes

echo(2**ceil(log(log(1+$argn,2),2))-2?:2)+2;

Run like this:

echo 16 | php -R 'echo(2**ceil(log(log(1+$argv[1],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

Answer 21

Octave, 40 36 31 29 bytes

Simple anonymous function. It is assumed that the input value is an integer - see the caveat at the end.

@(a)(b=2.^[0 2:6])(a<2.^b)(1)

The code works as follows:

• First an array of the allowed bit lengths (1,4,8,16,32,64) is created and saved to b.

• Next we find the number of bits required to store the input number a by comparing with the maximum size of each container in b to see which are big enough.

• We then use the resulting index vector to extract the container size from b again.

• Finally we take the first element in the resulting array which will be the smallest container possible.

You can try it online here.

Simply run the following code, and then do ans(x).

---

The only caveat with this is that double precision is used for constants by default which means that it only works with numbers up to the highest value representable by a double precision float that is less than 2^64.

This can be fixed by ensuring that the number that is supplied to the function is an integer rather than a double. This can be achieved by calling the function for example with: ans(uint64(x)).

Answer 22

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

Answer 23

C, 71 52 bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}

Answer 24

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.

Answer 25

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)[0]
       2R^    -   2 ** i
          <   -  input < ^

Answer 26

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.