45
\$\begingroup\$

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.

\$\endgroup\$
  • 10
    \$\begingroup\$ This would be considerably easier if 2 was an output too... \$\endgroup\$ – ETHproductions Dec 28 '16 at 21:15
  • 1
    \$\begingroup\$ @ETHproductions It would but alas, it isn't (it took me far to long to write an algorithm that did it) \$\endgroup\$ – Blue Dec 28 '16 at 21:16
  • \$\begingroup\$ 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? \$\endgroup\$ – z0rberg's Dec 29 '16 at 10:48
  • 2
    \$\begingroup\$ Thanks! I realized it when I wrote the comment and edited it too late. I guess I need a rubber duck to talk to... \$\endgroup\$ – z0rberg's Dec 29 '16 at 10:53
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – Blue Dec 29 '16 at 18:01

26 Answers 26

3
\$\begingroup\$

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!

\$\endgroup\$
22
\$\begingroup\$

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)
\$\endgroup\$
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ – ElPedro Dec 28 '16 at 22:36
  • \$\begingroup\$ @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))? \$\endgroup\$ – dfernan Dec 29 '16 at 12:20
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – trichoplax Dec 29 '16 at 19:20
  • 1
    \$\begingroup\$ @trichoplax, that is right. Thanks for the explanation. \$\endgroup\$ – dfernan Dec 29 '16 at 20:52
12
\$\begingroup\$

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

Python, 53 50 49 bytes

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

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.

\$\endgroup\$
8
\$\begingroup\$

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

JavaScript (ES7), 35 bytes

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

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – ngenisis Dec 29 '16 at 19:25
  • 1
    \$\begingroup\$ This can actually be done entirely with BitLength. See my answer \$\endgroup\$ – ngenisis Dec 29 '16 at 20:12
4
\$\begingroup\$

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

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

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

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

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

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;}
\$\endgroup\$
  • 1
    \$\begingroup\$ I know I can make this shorter, Io do it when I'm at a computer. \$\endgroup\$ – Pavel Dec 28 '16 at 22:12
  • 2
    \$\begingroup\$ save 50 bytes: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64; \$\endgroup\$ – Mindwin Dec 29 '16 at 14:28
  • \$\begingroup\$ @Mindwin I know, but I'm traveling and won't have access to a computer for a while. I'll get around to it. \$\endgroup\$ – Pavel Dec 29 '16 at 20:53
  • \$\begingroup\$ Does the score make it a... love byte? \$\endgroup\$ – Engineer Toast Apr 3 '17 at 18:34
2
\$\begingroup\$

Haskell, 43 bytes

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

Ruby, 39 36 bytes

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

Thanks G B for helping golf

\$\endgroup\$
  • \$\begingroup\$ Should also work without parentheses. Also, the list could be 0,2,3,4,5,6 and using 1<<2**p. \$\endgroup\$ – G B Dec 29 '16 at 11:16
  • \$\begingroup\$ ... because then you could use 0,*2..6. \$\endgroup\$ – G B Dec 29 '16 at 12:48
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Cows quack Dec 29 '16 at 7:44
  • \$\begingroup\$ @KritixiLithos should be fixed now - sorry, my Java's gone rusty... \$\endgroup\$ – FlipTack Dec 29 '16 at 9:50
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nicely constructed! (Shame that the space is necessary.) \$\endgroup\$ – Greg Martin Dec 29 '16 at 21:17
2
\$\begingroup\$

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

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

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

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

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

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

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

C, 71 52 bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – dmckee Dec 29 '16 at 20:30
  • \$\begingroup\$ @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. \$\endgroup\$ – Steadybox Dec 29 '16 at 20:51
0
\$\begingroup\$

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

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

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.

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