Eine variable Anzahl von Bits ist ein Array von 0 oder mehr Bits. So [0, 1]ist eine variable Anzahl von Bits, aber so ist [].

Schreiben Sie eine Funktion oder ein Programm, das bei einer nichtnegativen Ganzzahl eine variable Anzahl von Bits zurückgibt, sodass jede Ganzzahl eine Eins-zu-Eins-Zuordnung (bijektiv) mit einem Array aufweist.

Es gibt unendlich viele solcher Zuordnungen. Sie können eine nach Belieben erstellen , aber es muss eins zu eins sein. Ihre Zuordnung muss für eine Ganzzahl beliebiger Größe konzeptionell eins zu eins sein. Es ist jedoch in Ordnung, wenn Ihre Implementierung für große Ganzzahlen aufgrund numerischer Typgrenzen in Ihrer bevorzugten Sprache (z int. B. Cs ) fehlschlägt .

Als ein Beispiel von dem, was nicht eine Abbildung einer Eins-zu-eins, die Auflistung ist einfach die binären Ziffern der ganzen Zahl. In einem solchen System wird 5 [1, 0, 1](oder 0b101), aber es ist nicht eins zu eins, weil 0b0101oder [0, 1, 0, 1]bedeutet auch 5.

Es sollte ziemlich offensichtlich sein, dass eine Zuordnung nicht eins zu eins ist, wenn eine Ganzzahl übersprungen wird (z. B. funktioniert sie nicht für 5), aber ich möchte klarstellen, dass das Überspringen eines variablen Bitarrays auch keine ist -zu eins. Sie müssen jedem möglichen variablen Bitarray zuordnen, einschließlich [].

Der kürzeste Code in Bytes gewinnt.

Gelee, 3 Bytes

‘BḊ

Gleiche Idee wie xnor: Karten 0 1 2 3 4 ...zu [] [0] [1] [0 0] [0 1] ...; Der Code ist im Grunde increment → binary → remove first.

Probieren Sie es online aus .

Python, 20 Bytes

lambda n:bin(~n)[4:]

Prüfung:

>> [bin(~n)[4:] for n in range(16)]
['', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111', '0000']

Wenn Sie dies tun, wird lambda n:bin(n+1)[3:]die Eingabe inkrementiert und dann die Binärdarstellung mit dem ersten entfernten Symbol verwendet ( [3:]da das Präfix aus 0bzwei Zeichen besteht). Da jede positive Zahl mit 1 in binär beginnt, ergibt dies eindeutig eine binäre Darstellung.

Ein Byte wird gespeichert, indem stattdessen das Bitkomplement verwendet wird ~n, um die Negation zu erhalten -(n+1), und das negative Vorzeichen entfernt wird, indem ein weiteres Symbol abgeschnitten wird.

Pyth, 5 Bytes

t.BhQ

Einfach eine Übersetzung von xnors Antwort in Pyth.

Qis eval () 'd input (), herhöht es, .Bkonvertiert es in eine binäre Zeichenfolge und tnimmt den "Schwanz" (der alles außer dem ersten Zeichen ist).

Haskell, 41 38 30 29 Bytes

l="":[b:x|x<-l,b<-"01"]
(l!!)

Anwendungsbeispiel: (l!!) 4-> "10".

Beginnen Sie mit der leeren Liste als erstem Element, gehen Sie träge durch die Liste und hängen Sie das aktuelle Element mit 0und mit 1davor an.

Bearbeiten: @xnor hat 3 11 Bytes gespeichert . Vielen Dank!

JavaScript (ES6), 29 Byte

x=>(~x).toString(2).slice(2)

Gleiche Idee wie xnor.

f=x=>(~x).toString(2).slice(2);
[...Array(100)].map((v,x)=>A.textContent+=x + ': ' + f(x) + '\n')

<pre id=A></pre>

Jolf, 4 Bytes

Probieren Sie es hier aus!

wBhj
  hj  input + 1
 B    converted to binary
w     with first removed.

Sehr einfache Strategie, zufällig auch die kürzeste.

Haskell, 35 Bytes

h 1=[]
h n=mod n 2:h(div n 2)
h.(+1)

In Haskell ist keine Binärdatei integriert, daher erfolgt die (umgekehrte) Konvertierung manuell. Um die anfängliche 1 zu entfernen, wurde der Basisfall 1in die leere Liste umgewandelt.

Bearbeiten: Sparte ein Byte durch Konjugieren mit dem +1.

h 0=[]
h m=1-mod m 2:h(div(m+1)2-1)

C 40 Bytes

f(n){if(++n/2)putchar(n%2+48),f(n/2-1);}

Konvertiert die Eingabe wie die anderen Antworten in die bijektive Basis 2 (mit Symbolen 0und 1).

ideone es!