Zmienna liczba bitów to tablica 0 lub więcej bitów. Podobnie [0, 1]jest ze zmienną liczbą bitów, ale tak też jest [].

Napisz funkcję lub program, który przy nieujemnej liczbie całkowitej zwraca zmienną liczbę bitów, dzięki czemu każda liczba całkowita ma odwzorowanie jeden na jeden (bijective) z tablicą.

Istnieje nieskończona ilość takich mapowań, możesz dowolnie je budować, ale musi to być jeden na jeden. Twoje mapowanie musi być koncepcyjnie jeden na jeden dla liczby całkowitej o dowolnym rozmiarze, ale jest OK, jeśli twoja implementacja nie powiedzie się dla dużych liczb całkowitych z powodu ograniczeń liczbowych typów w preferowanym języku (np. C int).

Przykładem tego, co nie jest mapowaniem jeden na jeden, jest po prostu wyświetlenie cyfr binarnych liczby całkowitej. W takim systemie 5 staje się [1, 0, 1](lub 0b101), ale nie jest to jeden do jednego, ponieważ 0b0101lub [0, 1, 0, 1]też oznacza 5.

Powinno być całkiem oczywiste, że mapowanie nie jest jeden do jednego, jeśli pomija liczbę całkowitą (np. Nie działa dla 5), ​​ale chciałbym jasno powiedzieć, że pomijanie zmiennej tablicy bitów również nie jest jednym -do jednego. Musisz odwzorować na każdą możliwą zmienną tablicę bitów, w tym [].

Najkrótszy kod w bajtach wygrywa.

Galaretka, 3 bajty

‘BḊ

Ten sam pomysł, co xnor: mapuje 0 1 2 3 4 ...na [] [0] [1] [0 0] [0 1] ...; kod jest w zasadzie increment → binary → remove first.

Wypróbuj online .

Python, 20 bajtów

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

Test:

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

Wykonanie lambda n:bin(n+1)[3:]zwiększa dane wejściowe, a następnie pobiera reprezentację binarną z usuniętym pierwszym symbolem ( [3:]ponieważ prefiks 0bto dwa znaki znaku). Ponieważ każda liczba dodatnia zaczyna się od 1 w postaci binarnej, to wyjątkowo daje reprezentację binarną.

Bajt jest zapisywany przez użycie dopełniacza bitowego w ~ncelu uzyskania negacji -(n+1)i usunięcie znaku ujemnego przez odcięcie jeszcze jednego symbolu.

Pyth, 5 bajtów

t.BhQ

Po prostu tłumaczenie odpowiedzi xnora na Pyth.

Qjest eval () 'd input (), hinkrementuje go, .Bkonwertuje na ciąg binarny i tbierze „ogon” (czyli wszystko oprócz pierwszego znaku).

Haskell, 41 38 30 29 bajtów

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

Przykład użycia: (l!!) 4-> "10".

Począwszy od pustej listy jako pierwszy element, chodzić leniwie przez liście i dołączyć bieżący element z 0i 1przed nim.

Edycja: @xnor zapisał 3 11 bajtów. Dzięki!

JavaScript (ES6), 29 bajtów

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

Taki sam pomysł jak 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 bajty

Wypróbuj tutaj!

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

Bardzo prosta strategia, również najkrótsza.

Haskell, 35 bajtów

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

Haskell nie ma wbudowanego pliku binarnego, więc konwersja (odwrócona) jest wykonywana ręcznie. Aby usunąć początkową 1, przypadek podstawowy 1przekształcił się w pustą listę.

Edycja: Zapisano bajt, koniugując przez +1zamiast.

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

C, 40 bajtów

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

Konwertuje dane wejściowe na bazę bijective 2 (z symbolami 0i 1), podobnie jak inne odpowiedzi.

ideone to!