Ein bisschen, ein Knabbern oder ein Byte?

45

Inspiriert von dieser Herausforderung

Geben Sie bei einer Ganzzahl im Bereich 0 <= n < 2**64den Container mit der Mindestgröße aus, in den er passen kann

  • Bit: 1
  • Knabbern: 4
  • Byte: 8
  • kurz: 16
  • int: 32
  • lang: 64

Testfälle:

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

Das ist , also gewinnt die kürzeste Antwort in Bytes.

Blau
quelle
10
Dies wäre wesentlich einfacher, wenn auch 2eine Ausgabe wäre ...
ETHproductions
1
@ETHproductions Es wäre aber leider nicht (es dauerte viel zu lange, um einen Algorithmus zu schreiben, der es tat)
Blue
Ich wünschte, ich hätte das Problem verstanden. ... warte, alles was es will ist die Menge an Bits, die benötigt wird, um die Zahl aufzunehmen, auf die nächste Grundstruktur gerundet?
z0rbergs
2
Vielen Dank! Ich habe es bemerkt, als ich den Kommentar geschrieben und zu spät bearbeitet habe. Ich schätze, ich brauche eine Gummiente, mit der ich sprechen kann ...
z0rbergs
2
@Daniel die Antworten hier gehen ganz anders auf die andere Frage ein. Wenn ich "inspiriert von" sage, bedeutet das nicht "Duplikat von". Keine Antworten konnten geringfügig geändert werden, damit sie für diese Frage gültig sind.
Blau,

Antworten:

3

05AB1E , 10 Bytes

bg.²îD1Q+o

Erläuterung

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

Probieren Sie es online!

Osable
quelle
22

Python, 39 Bytes

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

Zählt, wie oft man die Quadratwurzel ziehen muss, num darunter zu sein 16, mit einem speziellen Gehäuse, um Ausgaben von 2 zu vermeiden.

Wenn 2 enthalten wären, könnten wir tun

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

mit True für 1.


41 Bytes:

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

Verdoppelt wiederholt den Exponenten ibis 2**i>n. Springt von i=1bis, i=4indem ein zusätzliches Bit verschoben wird, wenn ies ungerade ist.

Alt 45 Bytes:

f=lambda n,i=4:4**(n>1)*(2**i>n)or 2*f(n,i*2)
xnor
quelle
7
Es überrascht mich immer wieder, wie Sie so viele Lösungen für ein Problem finden können. Grundsätzlich habe ich als Programmierer gelernt, eine Lösung für ein Problem zu finden und damit zu arbeiten, bis es funktioniert. Ich denke, ich muss noch viel über Golf lernen! Respekt.
ElPedro
@xnor, wie wird Ihre erste Antwort ausgegeben, 1wenn die Quadratwurzel von 0 oder 1 immer 1 ist (unendliche Rekursivität in or 2*f(n**.5))?
Dfernan
2
@dfernan Ich glaube das Teil nach dem orwird nur ausgewertet wenn das Teil vorher etwas falsch bewertet wird (null). Für n = 0 und für n = 1 wird n>1ausgewertet bis False, was in einem numerischen Ausdruck als Null behandelt wird, und n<16ausgewertet bis True, was in einem numerischen Ausdruck als Eins behandelt wird. So 4**(n>1)*(n<16)ist 1.
Trichoplax
1
@trichoplax, das ist richtig. Danke für die Erklärung.
29.
12

J, 19 Bytes

Monadisches Verb, das die Zahl rechts aufnimmt und die Behältergröße ausspuckt. Es gibt zwei äquivalente Schreibweisen, also habe ich beide eingeschlossen.

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

Erklärt durch 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

Was cool ist, ist, dass wir in J zwei verschiedene Arten sehen 2^., Logarithmus 2 zu nehmen. Die erste ist der offensichtliche , ein numerischer Logarithmus. Die zweite ist #@#:, die als "Länge der Basis-2-Darstellung" gelesen werden kann. Dies ist fast gleichbedeutend mit einem Plus-Stockwerk-von-Log-Basis-2, mit der Ausnahme, dass #:0es sich um die Liste mit einem Element handelt 0, die genau das ist, was wir wollen. Dies schlägt 1+2<.@^.1&>.um 8 Bytes.

Im Einsatz bei der 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

Alte, zu clevere 20-Byte-Lösung.

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
algorithmshark
quelle
9

Python, 53 50 49 Bytes

lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]
orlp
quelle
1
lambda n:[w for w in[1,4,8,16,32,64]if n<2**w][0]ist ein Byte kürzer
Blau
Wollte gerade etwas ähnliches posten. +1
ElPedro
8

Mathematica, 44 39 38 Bytes

Danke @orlp für 5 Bytes und @MartinEnder für 1 Byte.

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

Findet als erstes die Elemente in der Liste {1, 4, 8, 16, 32, 64}, sodass 2 ^ number größer als die Eingabe ist.

JungHwan min
quelle
8

Pip , 19 Bytes

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

Probieren Sie es online!

Wie es funktioniert

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

JavaScript (ES7), 35 Byte

n=>[1,4,8,16,32,64].find(b=>2**b>n)
Neil
quelle
2
Eine rekursive Version wie f=(n,b=1)=>2**b>n&&b-2?b:f(n,b*2)sollte etwas kürzer sein.
Arnauld
6

Mathematica, 46 43 38 Bytes

Vielen Dank an JungHwan Min und Martin Ender für die Einsparung von 3 Bytes! Danke an ngenisis für die großen 5-Byte-Einsparungen!

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

Unbenannte Funktion, die eine nicht negative Ganzzahl als Eingabe verwendet und eine positive Ganzzahl zurückgibt. BitLength@#berechnet die Anzahl der Bits in der Eingabe und 2^⌈Log2@...⌉berechnet dann die kleinste Potenz von 2, die mindestens so groß ist wie die Anzahl der Bits. Zum Schluss wird /.{2->4,0->1}auf den Sonderfall geachtet, dass zwischen Bit und Nybble kein "Niblit" besteht, und die Antwort für die seltsame Eingabe korrigiert 0.

Greg Martin
quelle
2
Sparen Sie 3 Bytes, indem Sie BitLength@#anstelle von verwenden ⌊1+Log2@#⌋. Anstatt durch zu 1ersetzen 0, können Sie dann ersetzen , indem Sie weitere 2 Bytes speichern, und Sie sind zuerst gebunden.
Genisis
1
Das kann man eigentlich ganz mit machen BitLength. Siehe meine Antwort
Genisis
4

Julia, 40 Bytes

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

Dies ist eine anonyme Funktion, die ein Array der Zweierpotenzen von 0 bis 6 (mit Ausnahme von 2) generiert und es nur auf die Elemente x filtert, sodass 2 x größer als die Eingabe ist. Das erste solche Element ist die Antwort. Leider erfordert dies das Hochstufen von 2 auf a BigInt, um einen Überlauf auf x = 64 zu vermeiden .

Dies ist der Python-Antwort von orlp eigentlich ziemlich ähnlich, obwohl ich es nicht gesehen habe, bevor ich mir diesen Ansatz ausgedacht habe.

Probieren Sie es online!

Alex A.
quelle
4

Perl 6 , 30 Bytes

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

+<ist Perl 6's linker Bitverschiebungsoperator, den viele andere Sprachen aufrufen <<.

Sean
quelle
4

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)
xnor
quelle
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
quelle
1
Ich weiß, ich kann das kürzer machen, ich mache es, wenn ich an einem Computer bin.
Pavel
2
50 Bytes speichern: return a<2?1:a<5?4:a<9?8:a<17?16:a<33?32:64;
Mindwin
@ Mindwin Ich weiß, aber ich reise und habe für eine Weile keinen Zugang zu einem Computer. Ich werde mich darum kümmern.
Pavel
Macht die Partitur es zu einem ... Liebesbyte ?
Ingenieur Toast
2

Haskell, 43 Bytes

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

Ruby, 39 36 Bytes

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

Vielen Dank, GB, dass Sie beim Golfen helfen

Alexis Andersen
quelle
Sollte auch ohne Klammern funktionieren. Die Liste könnte auch 0,2,3,4,5,6 lauten und 1 << 2 ** p enthalten.
GB
... denn dann könnten Sie 0, * 2..6 verwenden.
GB
2

Java 8, 65-55 Bytes

Dies ist ein Lambda-Ausdruck, der ein nimmt longund ein zurückgibt int. Nie zuvor in Java Golf gespielt, daher sollte dies leicht zu schlagen sein:

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

Probieren Sie es online!


Für 47 Bytes könnten wir haben:

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

Allerdings 1L<<iüberläuft für Rückgabewerte größer als 32, so dass diese für die endgültige Testfall ausfällt.

FlipTack
quelle
1
Dies wird zurückgegeben, 4wenn getestet wird, 16wann es 8 zurückgeben soll. Sie können diese Lösung auch weiterhin spielen, indem Sie die Klammern entfernen, i<<=1+i%2;da {}die while-Schleife ohne s nur die nächste Zeile
ausführt
@KritixiLithos sollte jetzt behoben sein - Entschuldigung, mein Java ist verrostet ...
FlipTack
2

Mathematica, 30 Bytes

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

Erläuterung:

Sei Ndie Menge der nichtnegativen ganzen Zahlen. Definieren Sie zwei Funktionen auf N, BitLengthund NextPowerwie folgt dar :

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

Diese Lösung berechnet im Wesentlichen NextPower(BitLength(n))eine ganze Zahl n >= 0. Denn n > 0wir können das NextPower(n) = 2^BitLength(n-1)so sehen NextPower(BitLength(n)) = 2^BitLength(BitLength(n)-1).

Jetzt BitLengthstimmt der Mathematica -Code mit der Definition überein, für die ich angegeben habe n >= 0. Für n < 0, BitLength[n] == BitLength[BitNot[n]] == BitLength[-1-n]so BitLength[-1] == BitLength[0] == 0. So bekommen wir die gewünschte Antwort von 1für n==0.

Da wir direkt von Bit zu Nibbeln springen, müssen wir Antworten von 2durch ersetzen 4.

Genisis
quelle
1
Schön gebaut! (Schade, dass der Raum notwendig ist.)
Greg Martin
2

Bash, 49 Bytes, 48 Bytes

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

oder

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

Speichern Sie in einem Skript und übergeben Sie die zu testende Nummer als Argument.

Bearbeiten: Ersetzt || mit |, was funktioniert, weil die Argumente immer 0 oder 1 sind.

Hinweis: Dies funktioniert für ganze Zahlen bis zur größten positiven Ganzzahl, die Ihre Version von bash verarbeiten kann. Wenn ich Zeit habe, ändere ich sie so, dass sie in Versionen von Bash, die 32-Bit-Arithmetik mit Vorzeichen verwenden, bis zu 2 ^ 64-1 funktioniert.

In der Zwischenzeit ist hier eine 64-Byte-Lösung, die für beliebig große Zahlen (in jeder Bash-Version) funktioniert:

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

Gestapelt, 34 30 Bytes

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

oder

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

Der erste nimmt Eingaben in den TOS entgegen und lässt Ausgaben im TOS; der zweite ist eine Funktion. Probieren Sie es hier aus!

Erläuterung

@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

Hier ist ein Beispiel für die Arbeit an der Replik :

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

Testfälle

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

Oder als volles Programm:

{!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
quelle
2

Schläger 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)))

Andere Versionen:

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

und mit Stringlänge:

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

Testen:

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

Ausgabe:

1
1
4
4
8
8
16
32
64
rnso
quelle
1

Octave, 40 36 31 29 Bytes

Einfache anonyme Funktion. Es wird davon ausgegangen, dass der Eingabewert eine Ganzzahl ist - siehe Warnung am Ende.

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

Der Code funktioniert wie folgt:

  • Zunächst wird ein Array der zulässigen Bitlängen (1,4,8,16,32,64) erstellt und in gespeichert b.

  • Als nächstes ermitteln wir die Anzahl der Bits, die zum Speichern der Eingabenummer erforderlich sind, aindem wir die maximale Größe jedes Containers in vergleichen b, um festzustellen , welche ausreichend groß sind.

  • Wir verwenden dann den resultierenden Indexvektor, um die Containergröße berneut zu extrahieren .

  • Schließlich nehmen wir das erste Element im resultierenden Array, das der kleinstmögliche Container ist.

Sie können es hier online ausprobieren .

Führen Sie einfach den folgenden Code aus, und führen Sie dann aus ans(x).


Die einzige Einschränkung dabei ist, dass für Konstanten standardmäßig die doppelte Genauigkeit verwendet wird. Dies bedeutet, dass nur Zahlen mit dem höchsten Wert verwendet werden können, der durch einen Gleitkommawert mit doppelter Genauigkeit von weniger als 2 ^ 64 darstellbar ist.

Dies kann behoben werden, indem sichergestellt wird, dass die an die Funktion übergebene Zahl eine Ganzzahl und keine Doppelzahl ist. Dies kann erreicht werden, indem die Funktion zum Beispiel mit: aufgerufen wird ans(uint64(x)).

Tom Carpenter
quelle
1

PHP, 49 46 44 Bytes

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

Laufen Sie wie folgt:

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

Erläuterung

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.

Optimierungen

  • 3 Bytes gespart, indem die $r=Zuordnung aufgehoben wurde
  • 2 Bytes mit gespeichert -R, um $argnverfügbar zu machen
aross
quelle
1

CJam , 18 Bytes

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

Probieren Sie es online!

Erläuterung

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
Geschäfts-Katze
quelle
0

C 71 52 Bytes

i;f(long long n){for(i=1;n>>i;i*=2);return i-2?i:4;}
Steadybox
quelle
Würde eine Eingabe von (1<<15)+1oder mehr dies nicht aufgrund des signierten Verhaltens von long longunterbrechen? Der Typ, den Sie wirklich wollen, ist uint64_tderjenige, #include <stdint.h>der es erfordert, und der im Vergleich zu den anderen immer noch ein Verlierer ist unsigned long long! Header sind der Fluch des Golfsports in c.
dmckee
@dmckee Ich denke, es könnte kaputt gehen, aber es scheint zumindest auf meinem Computer zu funktionieren. Ich habe kein Beispiel gefunden, das nicht funktionieren würde. Ich habe überlegt, unsigned long longoder zu verwenden uint64_t, aber da es zu funktionieren scheint, long longbin ich mitgegangen.
Steadybox
0

QBIC , 27 Bytes

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

Erläuterung

:        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
quelle
0

Pyke, 13 Bytes

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

Probieren Sie es hier aus!

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 < ^
Blau
quelle
0

PHP, 43 Bytes

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

Laufen Sie mit echo <number> | php -R '<code>' .

Endlosschleifen $i, bis 2**(2**$i)größer als die Eingabe ist. (Tweak: <<anstatt **Parens zu eliminieren)
Nach der Schleife ist $ i eins zu hoch; es wird also ein dekrement vor der berechnung der ausgabe
- aber nicht für $i==2.

Titus
quelle