Um pouco, uma mordidela ou byte?

45

Inspirado por este desafio

Dado um número inteiro no intervalo 0 <= n < 2**64, imprima o contêiner de tamanho mínimo em que ele pode caber

  • bit: 1
  • mordidela: 4
  • byte: 8
  • curta: 16
  • int: 32
  • longo: 64

Casos de teste:

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

Isso é , então a resposta mais curta em bytes vence.

Azul
fonte
10
Isso seria consideravelmente mais fácil se 2também houvesse uma saída ...
ETHproductions
1
@ETHproductions Seria, mas infelizmente não é (demorei muito tempo para escrever um algoritmo que o fez) #
Blue
Eu gostaria de entender o problema. ... espera, tudo o que deseja é a quantidade de bits necessária para conter o número, arredondado para a próxima estrutura fundamental?
de z0rberg
2
Obrigado! Eu percebi isso quando escrevi o comentário e o editei tarde demais. Eu acho que preciso de um pato de borracha para falar com ...
de z0rberg
2
@ Daniel, as respostas aqui adotam uma abordagem completamente diferente da outra pergunta. Quando digo "inspirado por", não significa "duplicado de". Nenhuma resposta pode ser modificada trivialmente para ser válida para esta pergunta #
Blue

Respostas:

3

05AB1E , 10 bytes

bg.²îD1Q+o

Explicação

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

Experimente online!

Osable
fonte
22

Python, 39 bytes

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

Conta quantas vezes é necessário obter a raiz quadrada para nestar abaixo 16, com uma caixa especial para evitar saídas 2.

Se 2 fossem incluídos, poderíamos fazer

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

com True para 1.


41 bytes:

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

Dobra repetidamente o expoente iaté 2**i>n. Pula de i=1para i=4deslocando um bit adicional quando ié ímpar.

Alt 45 bytes:

f=lambda n,i=4:4**(n>1)*(2**i>n)or 2*f(n,i*2)
xnor
fonte
7
Nunca deixa de me surpreender como você pode encontrar tantas soluções para um problema. Basicamente, como programador, aprendi a encontrar uma solução para um problema e a trabalhar com ele até que funcione. Acho que ainda tenho muito a aprender sobre golfe! Respeito.
ElPedro
@ xnor, como sua primeira resposta é exibida 1quando a raiz quadrada de 0 ou 1 é sempre 1 (recursividade infinita em or 2*f(n**.5))?
dfernan
2
@ dfernan Eu acredito que a parte após a orsó é avaliada se a parte anterior for avaliada como algo falso (zero). Para n = 0 e para n = 1, n>1avalia como False, que é tratado como zero em uma expressão numérica, e n<16avalia como True, que é tratado como um em uma expressão numérica. Assim 4**(n>1)*(n<16)é 1.
trichoplax
1
@trichoplax, isso mesmo. Obrigada pelo esclarecimento.
dfernan
12

J, 19 bytes

Verbo monádico, pegando o número à direita e cuspindo o tamanho do contêiner. Existem algumas maneiras equivalentes de escrever, então eu incluí as duas.

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

Explicado por explosão:

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

O legal é que vemos duas maneiras diferentes de obter a base de log 2 em J. A primeira é a óbvia 2^., que é um logaritmo numérico. A segunda é #@#:, que pode ser lida como "comprimento da representação da base 2". Isso é quase equivalente a um mais-andar-de-log-base-2, exceto que #:0é a lista de um elemento 0, que é exatamente o que queremos. Isso bate 1+2<.@^.1&>.em 8 bytes.

Em uso no 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

Solução antiga e excessivamente inteligente de 20 bytes.

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
algoritmshark
fonte
9

Python, 53 50 49 bytes

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]
orlp
fonte
1
lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]é um byte mais curto
Azul
Estava prestes a publicar algo semelhante. 1
ElPedro
8

Mathematica, 44 39 38 bytes

Obrigado @orlp por 5 bytes e @MartinEnder por 1 byte.

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

Localiza os primeiros elementos da lista, de {1, 4, 8, 16, 32, 64}modo que o número 2 ^ seja maior que a entrada.

JungHwan Min
fonte
8

Pip , 19 bytes

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

Experimente online!

Como funciona

                     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
DLosc
fonte
7

JavaScript (ES7), 35 bytes

n=>[1,4,8,16,32,64].find(b=>2**b>n)
Neil
fonte
2
Uma versão recursiva como f=(n,b=1)=>2**b>n&&b-2?b:f(n,b*2)deve ser um pouco mais curta.
Arnauld
6

Mathematica, 46 43 38 bytes

Agradecemos a JungHwan Min e Martin Ender por economizar 3 bytes! Obrigado à ngenisis por uma grande economia de 5 bytes!

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

Função sem nome, recebendo um número inteiro não negativo como entrada e retornando um número inteiro positivo. BitLength@#calcula o número de bits na entrada e depois 2^⌈Log2@...⌉calcula a menor potência de 2 que é pelo menos tão grande quanto o número de bits. Finalmente, /.{2->4,0->1}cuida do caso especial de que não há "niblit" entre bit e nybble e também corrige a resposta para a entrada estranha 0.

Greg Martin
fonte
2
Salve 3 bytes usando em BitLength@#vez de ⌊1+Log2@#⌋. Então, em vez de substituir por 1você 0, você pode substituir , economizando outros 2 bytes e você fica empatado em primeiro lugar.
Ngenisis
1
Isso pode realmente ser feito inteiramente com BitLength. Veja minha resposta
ngenisis
4

Julia, 40 bytes

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

Essa é uma função anônima que gera uma matriz dos poderes de 2 de 0 a 6, excluindo 2, e a filtra apenas aos elementos x, de modo que 2 x seja maior que a entrada. O primeiro desses elementos é a resposta. Infelizmente, isso exige a promoção de 2 a BigIntpara evitar o estouro de x = 64.

Na verdade, isso é bastante semelhante à resposta Python do orlp, embora eu não a tenha visto antes de inventar essa abordagem.

Experimente online!

Alex A.
fonte
4

Perl 6 , 30 bytes

{first 1+<*>$_,1,4,8,16,32,64}

+<é o operador de deslocamento de bits esquerdo do Perl 6, que muitos outros idiomas chamam <<.

Sean
fonte
4

Haskell, 31 bytes

f n=[2^i|i<-0:[2..],2^2^i>n]!!0

Alt de 32 bytes:

f n|n<2=1|n<16=4|1>0=2*f(sqrt n)
xnor
fonte
2

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;}
Pavel
fonte
1
Eu sei que posso diminuir isso, faço quando estou em um computador.
Pavel
2
salve 50 bytes: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64;
Mindwin
@ Mindwin eu sei, mas estou viajando e não vou ter acesso a um computador por um tempo. Eu vou dar um jeito nisso.
Pavel
A pontuação o torna um ... byte de amor ?
Engineer Toast
2

Haskell, 43 bytes

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

Ruby, 39 36 bytes

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

Obrigado GB por ajudar o golfe

Alexis Andersen
fonte
Também deve funcionar sem parênteses. Além disso, a lista pode ser 0,2,3,4,5,6 e usar 1 << 2 ** p.
GB
... porque então você pode usar 0, * 2..6.
GB
2

Java 8, 65 55 bytes

Esta é uma expressão lambda que pega longae retorna an int. Nunca jogou golfe em Java antes, portanto, isso deve ser facilmente superável:

x->{int i=1;while(Math.pow(2,i)<=x)i<<=1+i%2;return i;}

Experimente online!


Para 47 bytes , poderíamos ter:

x->{int i=1;while(1L<<i<=x)i<<=1+i%2;return i;}

No entanto, 1L<<iestouros excessivos para valores de retorno maiores que 32, portanto, isso falha no caso de teste final.

FlipTack
fonte
1
Isso retorna 4quando testado com 16quando deve retornar 8. Além disso, você ainda pode jogar golfe nessa solução removendo os colchetes, i<<=1+i%2;pois sem {}s, o loop while apenas executa a próxima linha
Kritixi Lithos
@KritixiLithos deve ser corrigido agora - desculpe, meu enferrujado ido de Java ...
FlipTack
2

Mathematica, 30 bytes

2^(f=BitLength)[f@#-1]/. 2->4&

Explicação:

Let NSer o conjunto de números inteiros não negativos. Definir duas funções em N, BitLengthe NextPowercomo segue:

BitLength(n) := min {x in N : 2^x - 1 >= n}
NextPower(n) := 2^(min {x in N : 2^x >= n})

Esta solução calcula essencialmente NextPower(BitLength(n))dado um número inteiro n >= 0. Pois n > 0, podemos ver isso NextPower(n) = 2^BitLength(n-1), então NextPower(BitLength(n)) = 2^BitLength(BitLength(n)-1).

Agora, o Mathematica BitLengthinterno concorda com a definição que eu dei n >= 0. Por n < 0, BitLength[n] == BitLength[BitNot[n]] == BitLength[-1-n], então BitLength[-1] == BitLength[0] == 0. Assim, obtemos a resposta desejada de 1para n==0.

Já que pulamos direto de pouco para mordiscar, temos que substituir as respostas de 2por 4.

ngenisis
fonte
1
Bem construído! (Pena que o espaço é necessário.)
Greg Martin
2

bash, 49 bytes 48 bytes

for((y=1;$[y==2|$1>=1<<y];$[y*=2])){ :;};echo $y

ou

for((y=1;$[y==2|$1>=1<<y];)){ y=$[y*2];};echo $y

Salve em um script e passe o número a ser testado como argumento.

Editar: Substituído || com |, que funciona porque os argumentos são sempre 0 ou 1.

Nota: Isso funciona para números inteiros até o maior número positivo positivo que sua versão do bash pode manipular. Se tiver tempo, modificarei para que funcione até 2 ^ 64-1 em versões do bash que usam aritmética de 32 bits.

Enquanto isso, aqui está uma solução de 64 bytes que funciona para números arbitrariamente grandes (em qualquer versão do bash):

for((x=`dc<<<2o$1n|wc -c`;$[x==2||x&(x-1)];$[x++])){ :;};echo $x
Mitchell Spector
fonte
2

Empilhados, 34 30 bytes

@n 1 2 6|>2\^,:n 2 log>keep 0#

ou

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

O primeiro recebe entrada no TOS e deixa a saída no TOS; o segundo é uma função. Experimente aqui!

Explicação

@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

Aqui está um exemplo dele trabalhando na repl :

> 8    (* input *)
(8)
> @n 1 2 6|>2\^,:n 2 log>keep 0#    (* function *)
(4)
>    (* output *)
(4)

Casos de teste

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

Ou, como um programa completo:

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

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

out
Conor O'Brien
fonte
2

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

Outras versões:

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

e usando o comprimento da string:

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

Testando:

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

Resultado:

1
1
4
4
8
8
16
32
64
rnso
fonte
1

Oitava, 40 36 31 29 bytes

Função anônima simples. Supõe-se que o valor de entrada seja um número inteiro - veja a ressalva no final.

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

O código funciona da seguinte maneira:

  • Primeiro, uma matriz dos comprimentos de bits permitidos (1,4,8,16,32,64) é criada e salva em b.

  • A seguir, encontramos o número de bits necessários para armazenar o número de entrada acomparando com o tamanho máximo de cada contêiner bpara ver quais são grandes o suficiente.

  • Em seguida, usamos o vetor de índice resultante para extrair o tamanho do contêiner bnovamente.

  • Finalmente, pegamos o primeiro elemento na matriz resultante, que será o menor contêiner possível.

Você pode experimentá-lo online aqui .

Simplesmente execute o código a seguir e faça ans(x).


A única ressalva é que a precisão dupla é usada para constantes por padrão, o que significa que ela só funciona com números até o valor mais alto representável por um flutuador de precisão dupla menor que 2 ^ 64.

Isso pode ser corrigido garantindo que o número fornecido à função seja um número inteiro e não um duplo. Isto pode ser conseguido chamando a função por exemplo, com: ans(uint64(x)).

Tom Carpenter
fonte
1

PHP, 49 46 44 bytes

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

Execute assim:

echo 16 | php -R 'echo(2**ceil(log(log(1+$argv[1],2),2))-2?:2)+2;';echo

Explicação

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

  • Economizou 3 bytes ao se livrar da $r=tarefa
  • 2 bytes salvos usando -Rpara $argndisponibilizar
aross
fonte
1

CJam , 18 bytes

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

Experimente online!

Explicação

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
Gato de negócios
fonte
0

C, 71 52 bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
Steadybox
fonte
Uma entrada (1<<15)+1ou mais não quebraria isso por causa do comportamento assinado de long long? O tipo que você realmente quer é o uint64_tque precisa e #include <stdint.h>que ainda é um perdedor comparado a unsigned long long! Cabeçalhos são a proibição do golfe em c.
dmckee
@ DMCkee Eu acho que poderia quebrá-lo, mas parece funcionar pelo menos no meu computador. Não encontrei um exemplo que não funcionasse. Pensei em usar unsigned long longor uint64_t, mas, como parece funcionar long long, fui com ele.
Steadybox 29/12/16
0

QBIC , 27 bytes

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

Explicação

:        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.
steenbergh
fonte
0

Pyke, 13 bytes

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

Experimente aqui!

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 < ^
Azul
fonte
0

PHP, 43 bytes

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

Corra com echo <number> | php -R '<code>'.

faz um loop $iaté 2**(2**$i)ser maior que a entrada. (Ajuste: em <<vez de **eliminar parênteses)
Após o loop, $ i é um muito alto; portanto, obtém um decréscimo antes de calcular a saída
- mas não para $i==2.

Titus
fonte