Trochę, skubanie czy bajt?

45

Zainspirowany tym wyzwaniem

Biorąc pod uwagę liczbę całkowitą z zakresu 0 <= n < 2**64, wyprowadzaj pojemnik o minimalnej wielkości, w którym mógłby się zmieścić

  • bit: 1
  • skubać: 4
  • bajt: 8
  • krótki: 16
  • int: 32
  • długie: 64

Przypadki testowe:

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

To jest , więc wygrywa najkrótsza odpowiedź w bajtach.

niebieski
źródło
10
Byłoby to znacznie łatwiejsze, gdyby 2był również
efektem
1
@ETHproductions Byłoby, ale niestety nie jest (napisanie algorytmu, który to zrobił, zajęło mi dużo czasu)
Blue
Chciałbym zrozumieć problem. ... czekaj, wszystko czego chce to ilość bitów potrzebna do przechowywania liczby, zaokrąglona do następnej podstawowej struktury?
z0rberg,
2
Dzięki! Zrozumiałem to, kiedy napisałem komentarz i zredagowałem go zbyt późno. Chyba potrzebuję gumowej kaczki, aby porozmawiać z ...
z0rberg,
2
@Daniel odpowiedzi tutaj przyjmują zupełnie inne podejście do drugiego pytania. Kiedy mówię „zainspirowany”, nie oznacza to „duplikatu”. Żadnej odpowiedzi nie można w prosty sposób zmodyfikować, aby była ważna na to pytanie
Blue

Odpowiedzi:

3

05AB1E , 10 bajtów

bg.²îD1Q+o

Wyjaśnienie

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

Wypróbuj online!

Osable
źródło
22

Python, 39 bajtów

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

Zlicza, ile razy należy wziąć pierwiastek kwadratowy, naby znaleźć się poniżej 16, ze specjalną obudową, aby uniknąć wyników 2.

Gdyby uwzględniono 2, moglibyśmy to zrobić

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

z wartością True dla 1.


41 bajtów:

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

Wielokrotnie podwaja wykładnik wykładniczy ido 2**i>n. Pomija od i=1do i=4, przesuwając dodatkowy bit, gdy ijest nieparzysty.

Alt 45 bajtów:

f=lambda n,i=4:4**(n>1)*(2**i>n)or 2*f(n,i*2)
xnor
źródło
7
Nigdy nie przestaje mnie zadziwiać, w jaki sposób można znaleźć tak wiele rozwiązań problemu. Zasadniczo jako programista nauczyłem się znajdować rozwiązanie problemu i pracować z nim, aż zadziała. Chyba jeszcze wiele muszę się nauczyć o golfie! Szacunek.
ElPedro
@ xnor, w jaki sposób wypada twoja pierwsza odpowiedź, 1gdy pierwiastek kwadratowy z 0 lub 1 wynosi zawsze 1 (nieskończona rekurencyjność w or 2*f(n**.5))?
dfernan
2
@dfernan Wierzę, że część po orjest oceniana tylko wtedy, gdy część przedtem ocenia się na coś fałszywego (zero). Dla n = 0, a dla n = 1, n>1ocenia na False, który jest traktowany jako zero w wyrażeniu numerycznym, i n<16ocenia na True, który jest traktowany jako jeden w wyrażeniu numerycznym. Podobnie 4**(n>1)*(n<16)jest 1.
trichoplax
1
@ Trichoplax, to prawda. Dziękuję za wyjaśnienie.
dfernan
12

J, 19 bajtów

Czasownik monadyczny biorąc numer po prawej i wypluwając rozmiar pojemnika. Istnieje kilka równoważnych sposobów pisania, więc zawarłem oba.

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

Wyjaśnione przez wybuch:

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

Fajne jest to, że widzimy dwa różne sposoby przyjmowania logarytmicznej bazy 2 w J. Pierwszy jest oczywisty 2^., czyli logarytm numeryczny. Drugi to #@#:, który można odczytać jako „długość reprezentacji base-2”. Jest to prawie równoważne jednemu plus-piętro-log-base-2, z tym wyjątkiem, że #:0jest to lista jednoelementowa 0, która jest dokładnie tym, czego chcemy. To bije 1+2<.@^.1&>.o 8 bajtów.

W użyciu w 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

Stare, zbyt sprytne 20-bajtowe rozwiązanie.

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
algorytmshark
źródło
9

Python, 53 50 49 bajtów

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]
orlp
źródło
1
lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]jest o jeden bajt krótszy
Blue
Właśnie miałem opublikować coś podobnego. +1
ElPedro
8

Mathematica, 44 39 38 bajtów

Dzięki @orlp za 5 bajtów i @MartinEnder za 1 bajt.

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

Znajduje pierwsze elementy na liście w {1, 4, 8, 16, 32, 64}taki sposób, że liczba 2 ^ jest większa niż wartość wejściowa.

JungHwan Min
źródło
8

Pip , 19 bajtów

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

Wypróbuj online!

Jak to działa

                     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
źródło
7

JavaScript (ES7), 35 bajtów

n=>[1,4,8,16,32,64].find(b=>2**b>n)
Neil
źródło
2
Wersja rekurencyjna, taka jak, f=(n,b=1)=>2**b>n&&b-2?b:f(n,b*2)powinna być nieco krótsza.
Arnauld
6

Mathematica, 46 43 38 bajtów

Dzięki JungHwan Min i Martin Ender za oszczędność 3 bajtów! Dzięki ngenisis za duże 5-bajtowe oszczędności!

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

Nienazwana funkcja przyjmująca nieujemną liczbę całkowitą jako dane wejściowe i zwracająca liczbę całkowitą dodatnią. BitLength@#oblicza liczbę bitów na wejściu, a następnie 2^⌈Log2@...⌉oblicza najmniejszą potęgę 2, która jest co najmniej tak duża jak liczba bitów. Wreszcie /.{2->4,0->1}zajmuje się specjalnym przypadkiem, w którym nie ma „niblit” między bitem a nybble, a także naprawia odpowiedź na dziwne dane wejściowe 0.

Greg Martin
źródło
2
Zaoszczędź 3 bajty, używając BitLength@#zamiast ⌊1+Log2@#⌋. Wtedy zamiast zastąpienia z 1was może zastąpić 0, zapisując kolejne 2 bajty i jesteś przywiązany do pierwszego.
ngenisis
1
Można to właściwie zrobić całkowicie za pomocą BitLength. Zobacz moją odpowiedź
ngenisis,
4

Julia, 40 bajtów

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

Jest to anonimowa funkcja, która generuje tablicę potęg 2 od 0 do 6, wyłączając 2, i filtruje ją tylko do tych elementów x , że 2 x jest większe niż wejście. Pierwszym takim elementem jest odpowiedź. Niestety wymaga to podwyższenia 2 do a, BigIntaby uniknąć przepełnienia x = 64.

W rzeczywistości jest to dość podobne do odpowiedzi Python w orlp, chociaż nie widziałem jej przed wymyśleniem tego podejścia.

Wypróbuj online!

Alex A.
źródło
4

Perl 6 , 30 bajtów

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

+<jest operatorem przesunięcia bitów w lewo Perla 6, który nazywa wiele innych języków <<.

Sean
źródło
4

Haskell, 31 bajtów

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

32 bajty alt:

f n|n<2=1|n<16=4|1>0=2*f(sqrt n)
xnor
źródło
2

Java, 143 bajty.

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
źródło
1
Wiem, że mogę to skrócić, zrobię to, gdy będę przy komputerze.
Pavel
2
zapisz 50 bajtów: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64;
Mindwin
@Mindwin Wiem, ale podróżuję i przez pewien czas nie będę mieć dostępu do komputera. Zajmę się tym.
Pavel
Czy wynik sprawia, że ​​... bajt miłosny ?
Inżynier Toast
2

Haskell, 43 bajty

f x=head$filter((>x).(2^))$[1,4,8,16,32,64]
Alkalia
źródło
2

Rubin, 39 36 bajtów

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

Dzięki GB za pomoc w golfa

Alexis Andersen
źródło
Powinien także działać bez nawiasów. Ponadto lista może wynosić 0,2,3,4,5,6 i użyć 1 << 2 ** p.
GB
... ponieważ wtedy możesz użyć 0, * 2..6.
GB
2

Java 8, 65 55 bajtów

To wyrażenie lambda, które przyjmuje longa zwraca an int. Nigdy wcześniej nie grałem w golfa w Javie, więc powinno to być łatwe do pokonania:

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

Wypróbuj online!


Dla 47 bajtów moglibyśmy mieć:

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

Jednak 1L<<iprzepełnienie dla zwracanych wartości większych niż 32, więc nie powiedzie się to w przypadku ostatecznej skrzynki testowej.

FlipTack
źródło
1
To powraca, 4gdy testujemy, 16kiedy ma on powrócić 8. Ponadto możesz jeszcze i<<=1+i%2;{}
zagrać w
@KritixiLithos powinien zostać teraz naprawiony - przepraszam, moja Java jest zardzewiała ...
FlipTack
2

Mathematica, 30 bajtów

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

Wyjaśnienie:

Niech Nbędzie zbiorem nieujemnych liczb całkowitych. Zdefiniować dwie funkcje, na N, BitLengthi NextPower, co następuje:

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

To rozwiązanie zasadniczo oblicza na NextPower(BitLength(n))podstawie liczby całkowitej n >= 0. Dla n > 0widzimy, że NextPower(n) = 2^BitLength(n-1)tak NextPower(BitLength(n)) = 2^BitLength(BitLength(n)-1).

Teraz BitLengthwbudowana Mathematica zgadza się z podaną przeze mnie definicją n >= 0. Dla n < 0, BitLength[n] == BitLength[BitNot[n]] == BitLength[-1-n]tak BitLength[-1] == BitLength[0] == 0. W ten sposób otrzymujemy pożądaną odpowiedź 1na n==0.

Ponieważ pominąć prosto z kawałka skubać, musimy wymienić odpowiedziami 2z 4.

ngenisis
źródło
1
Ładnie wykonane! (Szkoda, że ​​przestrzeń jest konieczna.)
Greg Martin
2

bash, 49 bajtów 48 bajtów

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

lub

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

Zapisz w skrypcie i przekaż jako argument liczbę do przetestowania.

Edycja: Zastąpiony || z |, który działa, ponieważ argumentami są zawsze 0 lub 1.

Uwaga: Działa to dla liczb całkowitych do największej dodatniej liczby całkowitej, którą może obsługiwać twoja wersja bash. Jeśli będę miał czas, zmodyfikuję go tak, aby działał do 2 ^ 64-1 w wersjach bash, które używają 32-bitowej arytmetyki ze znakiem.

Tymczasem oto 64-bajtowe rozwiązanie, które działa na dowolnie duże liczby (w dowolnej wersji bash):

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

Skumulowane, 34 30 bajtów

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

lub

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

Pierwszy pobiera dane wejściowe do TOS i pozostawia dane wyjściowe w TOS; drugi jest funkcją. Wypróbuj tutaj!

Wyjaśnienie

@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

Oto przykład jego działania na replice :

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

Przypadki testowe

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

Lub jako pełny program:

{!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
źródło
2

Rakieta 45 bajtów

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

Nie golfowany:

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

Inne wersje:

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

i przy użyciu długości łańcucha:

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

Testowanie:

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

Wynik:

1
1
4
4
8
8
16
32
64
rnso
źródło
1

Oktawa, 40 36 31 29 bajtów

Prosta anonimowa funkcja. Zakłada się, że wartość wejściowa jest liczbą całkowitą - patrz zastrzeżenie na końcu.

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

Kod działa w następujący sposób:

  • Najpierw tworzona jest tablica dozwolonych długości bitów (1,4,8,16,32,64) i zapisywana w niej b.

  • Następnie znajdujemy liczbę bitów wymaganą do przechowywania liczby wejściowej apoprzez porównanie z maksymalnym rozmiarem każdego pojemnika, baby zobaczyć, które są wystarczająco duże.

  • Następnie wykorzystujemy uzyskany wektor indeksu, aby ponownie wyodrębnić rozmiar kontenera b.

  • Wreszcie bierzemy pierwszy element z wynikowej tablicy, która będzie najmniejszym możliwym pojemnikiem.

Możesz spróbować online tutaj .

Po prostu uruchom następujący kod, a następnie zrób ans(x).


Jedynym zastrzeżeniem jest to, że podwójna precyzja jest domyślnie używana dla stałych, co oznacza, że ​​działa tylko z liczbami do najwyższej wartości reprezentowanej przez zmiennoprzecinkowe podwójnej precyzji, która jest mniejsza niż 2 ^ 64.

Można to naprawić, upewniając się, że liczba podawana do funkcji jest liczbą całkowitą, a nie podwójną. Można to osiągnąć poprzez wywołanie funkcji na przykład: ans(uint64(x)).

Tom Carpenter
źródło
1

PHP, 49 46 44 bajtów

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

Uruchom tak:

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

Wyjaśnienie

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.

Poprawki

  • Zaoszczędzono 3 bajty, pozbywając się $r=zadania
  • Zapisano 2 bajty za pomocą, -Raby $argnudostępnić
aross
źródło
1

CJam , 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

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
Business Cat
źródło
0

C, 71 52 bajtów

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
Steadybox
źródło
Czy wejście (1<<15)+1lub więcej nie złamałoby tego z powodu podpisanego zachowania long long? Typ naprawdę chcesz to uint64_tco wymaga #include <stdint.h>co jest jeszcze przegrany w porównaniu unsigned long long! Główki są zmorą gry w golfa w c.
dmckee,
@dmckee Chyba może to zepsuć, ale wydaje się, że działa przynajmniej na moim komputerze. Nie znalazłem przykładu, który nie działałby. Myślałem o użyciu unsigned long longlub uint64_t, ale ponieważ wydaje się, że to działa long long, poszedłem z tym.
Steadybox
0

QBIC , 27 bajtów

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

Wyjaśnienie

:        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
źródło
0

Pyke, 13 bajtów

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

Wypróbuj tutaj!

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 < ^
niebieski
źródło
0

PHP, 43 bajty

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

Uruchom z echo <number> | php -R '<code>'.

zapętla $isię, aż 2**(2**$i)będzie większy niż wejście. (Tweak: <<zamiast **eliminować parens)
Po pętli $ i jest o jeden za wysoki; więc przed obliczeniem wyniku otrzymuje dekrement
- ale nie dla $i==2.

Tytus
źródło