Napisz najkrótszy kod, aby odwrócić kolejność bitów 32-bitowej liczby całkowitej.
Zasady:
- Zakłada się, że dane wejściowe są prawidłową liczbą całkowitą lub ekwiwalentem ciągu, jeśli Twój język nie obsługuje wartości liczbowych (np. Windows Batch).
- Dane wyjściowe muszą być prawidłową liczbą całkowitą lub ciągiem równoważnym, jeśli Twój język nie obsługuje wartości liczbowych (np. Windows Batch).
- Tylko biblioteka standardowa.
- Może to być funkcja lub pełny program.
- Dane wejściowe mogą pochodzić z
stdin
argumentu funkcji lub z niego. - Dane wyjściowe muszą mieć wartość
stdout
lub być zwracaną wartością. - Jeśli twój język ma wbudowaną lub standardową funkcję biblioteki, która wykonuje to w jednym kroku (np.
rbit
W zespole ARM), nie można jej użyć.
Przykłady:
Klawisz:
- dziesiętny
- dwójkowy
- (rewers)
- odwrócony binarny
- wyjście dziesiętne
Przykłady:
-90
(8-bitowy przykład dla demonstracji)10100110b
- (rewers)
01100101b
101
486
00000000000000000000000111100110b
- (rewers)
01100111100000000000000000000000b
1736441856
-984802906
11000101010011010001100110100110b
- (rewers)
01100101100110001011001010100011b
1704506019
Uwaga: pominięcia to darmowa gra. Jeśli tego nie powiedziałem i nie jest to jedna ze standardowych luk , to jest to całkowicie dozwolone.
Odpowiedzi:
Zestaw x86, 9 bajtów
W formie
33 C0 40 D1 E9 13 C0 73 FA
bajtów:, 9 bajtów.źródło
__fastcall
i nie miałemret
.Zespół MMIX (28 bajtów)
64-bitowe liczby
To łączy się z:
Jak to działa?
MOR
Instrukcji wykonuje mnożenie macierzy w dwóch 64-bitowych ilości stosowanych jako dwa 8x8 matryc logicznych. Liczba boolowska z cyframi abcdefghklmnopqr 2 jest używana jako macierz w następujący sposób:W
MOR
mnoży instruktażowe macierze reprezentowane przez swoich argumentów gdzie mnożenieand
i dodawanieor
. To jest:a ponadto:
która jest odwrotną kolejnością bitów oryginalnego numeru.
32-bitowe liczby
Jeśli chcesz tylko odwrócić liczbę 32-bitową zamiast liczby 64-bitowej, możesz użyć tej zmodyfikowanej metody:
zmontowane:
Pierwsze mnożenie macierzy działa w zasadzie tak:
odpowiedni oktabajt
#0000000001020408
ładujemy w pierwszych dwóch instrukcjach. Drugie mnożenie wygląda następująco:Odpowiedni oktabajt
#0102040810204080
tworzymy z pierwszej macierzy w następujący sposób:Drugie mnożenie odbywa się jak zwykle, wynikowy kod ma tę samą długość (28 bajtów).
źródło
POLY
Instrukcja VAX jest w zasadzie połączonym mnożeniem i dodawaniem z wbudowaną pętlą. Podobne rzeczy istnieją również we współczesnych architekturach (jak x86), ale zwykle nie mają wbudowanej pętli do oceny całego wielomianu na raz.80386 montaż (
1312 bajtów)Jako funkcja w składni AT&T przy użyciu konwencji wywoływania cdecl.
Ta funkcja składa się z następującej sekwencji bajtów:
Podzielony na instrukcje:
Działa to w ten sposób: w każdej z 32 iteracji pętli argument, który znajduje się w
4(%esp)
, jest przesunięty w prawo o jedną pozycję. Ostatni bit jest domyślnie przenoszony na flagę carry.adc
Instrukcja dodaje dwie wartości i dodaje wartość flagi przeniesienia do wyniku. Jeśli dodajesz wartość do siebie, tzn.%eax
Skutecznie przesuwasz ją w lewo o jedną pozycję. Jestadc %eax,%eax
to wygodny sposób na przesunięcie w lewo%eax
o jedną pozycję przy jednoczesnym przesunięciu zawartości flagi przenoszenia na bit niskiego rzędu.Powtarzam ten proces 32 razy, aby cała zawartość
4(%esp)
została zrzucona%eax
. Nigdy nie inicjowałem jawnie,%eax
ponieważ jego poprzednia zawartość jest przesuwana podczas pętli.źródło
C,
635248Orginalna wersja:
Zaktualizowana wersja (ze zmianami wprowadzonymi przez Allbeert , es1024 i Dennis ):
Uwaga: Ponieważ druga wersja pomija ustawienie
r=0
, kod zakłada, że anint
ma 32 bity. Jeśli to założenie jest fałszywe, funkcja najprawdopodobniej wygeneruje niepoprawny wynik, w zależności od początkowego stanur
wejścia do funkcji.Wersja ostateczna (z dalszymi zmianami sugerowanymi przez Dennisa i Alchymista ):
Uwaga: To stawia deklarację zmiennych roboczych
r
ii
do listy parametrów. Parametry są następujące:n
jest liczbą, która ma być odwrócona.r
ii
są zmiennymi roboczymi, które należy przekazać jako 0.źródło
int
typ funkcji, a także zmienić sięreturn r
na coś w rodzaju,i=r
ponieważ większość kompilatorów C zwykle pozostawia wynik ostatniej operacji w rejestrze zwrotnym. Dla mnie działało na gcc i cl.r(n){...}
zamiastr(int n){...}
int
wint r=0,i=32;
chyba przenieść je z organizmu funkcji.-1 >> 1
jest-1
dla AS i2**31 - 1
dla LS, podczas gdy-1 / 2
jest0
.r
, ai
jako argumenty? Zaoszczędziłby jeszcze trzy bajty ...Julia 0,2, 33 bajty
Robi to, jak to wygląda.
bits
daje bitową reprezentację (z uwzględnieniem uzupełnienia dwóch).parseint
nie przejmuje się uzupełnieniem dwóch, ale zwraca 32-bitową liczbę całkowitą, więc uzupełnienie dwóch jest obsługiwane przez przepełnienie.Według dzienników zmian
parseint
w Julii 0.3 dodano wykrywanie przepełnienia , więc to może już nie działać.źródło
Python 2, 50
Zasadniczo to samo, co moje rozwiązanie Pyth. Weź wejściowy mod 2 ** 32, przekonwertuj na 32-bitowy wypełniony plik binarny, odwróć, zamień żądło binarne z powrotem na dziesiętne i wydrukuj.
źródło
CJam, 15 bajtów
Wypróbuj online.
Użyty joker „Free game”: Wyjście zawsze będzie liczbą całkowitą bez znaku .
Przypadki testowe
Jak to działa
źródło
JavaScript (E6) 37
39 40 50Funkcja, wprowadzanie liczb i zwracanie odwróconej liczby.
Najbardziej podstawowy algorytm, prawdopodobnie można grać w golfa za pomocą inteligentnej sztuczki.Edytuj rekurencję zamiast pętli
Edytuj 2 Zgodnie z sugestią @bebe
k*2
zamiastk<<1
Edytuj 3 Coś, co w ogóle mi umknęło: jest to pełna 32-bitowa pętla, nie trzeba inicjować k. Dzięki @FUZxxl
To było
Testuj W konsoli FireFox, testuj używając liczb w OP i niektórych bardziej losowych liczb 16 i 32 bitowych
Przykład wyjścia testowego
źródło
b=k=0,R=v=>b++<32?R(v>>1,k+=k+(v&1)):k
do jednorazowego użytku iR=(v,b=0,k=0)=>b<32?R(v>>1,b+1,k+k+(v&1)):k
nadaje się do wielokrotnego użytkuk<<1
staje sięk*2
iv>>1
stajev/2
. działało dla 486. Nie wiem o innych przypadkach testowychx86, 10 bajtów
Zakłada się wejście w eax, wyjście w edx. (Ponadto, na wyjściu eax wynosi zero, a CF i ZF są ustawione, jeśli kogo to obchodzi).
Zamiast licznika, dodatkowy 1 jest wpychany na początku jako znacznik końca danych
źródło
ret
instrukcję powrotu z funkcji i zaimplementujesz cdecl (tj. Zmieniszrcr %eax
narcr 4(%esp)
ircl %edx
narcl %eax
), otrzymujesz jeden dodatkowy bajt naret
dwa kolejne bajty na odwołanie do pamięci. Mimo to miłe rozwiązanie.J (
171513 bajtów)Oto wyraźna definicja wyjaśniająca, co robi:
#: y
reprezentujey
jako liczbę podstawową 2, wykorzystując tyle miejsc, ile potrzeba.x {. y
pobiera|x
(wielkośćx
) przedmiotówy
, z przodu, jeślix
jest dodatnia, z tyłu, jeślix
jest ujemna. Jeśli weźmiemy więcej przedmiotów niż obecnie, wynik zostanie uzupełniony zerami._32 {. #: y
skutecznie uzupełnia#: y
do 32 bitów.|. y
przewracay
, ja. odwraca kolejność elementów wy
.#. y
interpretujey
jako liczbę podstawową 2.źródło
Dyalog APL , 10 bajtów
2⊥
od-base-2 z⌽
odwrócony⎕
wprowadzanie numeryczne⊤⍨
w systemie liczbowym składającym się z32/2
32 bityWypróbuj APL online!
źródło
Python - 89
Python reprezentuje po prostu ujemne liczby binarne
-0b{positive_number}
. Aby sobie z tym poradzić, uzupełnij liczby ujemne, a następnie XOR wszystkimi 1.Następnie utwórz ciąg liczb całkowitych w oparciu o format
{:032b}
zapewniający 32-bitową reprezentację liczby. Na koniec odwróć ciąg i zamień go z powrotem w liczbę całkowitą.EDYTOWAĆ
Dzięki @Martin Büttner za zwrócenie uwagi na problem uzupełnienia dwóch. Jeśli
n
kończy się na 1, to przez uzupełnienie do dwóch odwrócona wersja byłaby ujemna.Na szczęście, jak wyjaśniono powyżej, Python lubi ujemne liczby binarne w dość prosty sposób. Na szczęście
int
funkcja Pythona pozwala opcjonalnie podpisywać znaki w pierwszym argumencie.Więc teraz dodaj znak minus, jeśli
n
jest nieparzysty, aby spełnić uzupełnienie dwóch.źródło
['','-'][n%2]
jest'-'*(n%2)
.Pyth ,
333222Wyjaśnienie:
Golfy:
33 -> 32: Przeniesiono dodaj do przed cofnięciem, aby zapisać cytat końcowy.
32 -> 22: Używany Q mod 2 ^ 32 zamiast skomplikowanej maszyny. Połączono oba ciągi w jeden.
Przypadki testowe:
źródło
GNU dc, 27 bajtów
Wydajność:
Bash + coreutils, 45 bajtów
Wydajność:
Funkcja C, 89 bajtów
Taki sam pomysł, jak /codegolf//a/36289/11259 - przy użyciu kręcących się hacków Stanforda . Nie zamierzam wygrywać w golfa, ale mimo to interesujące:
Wydajność:
źródło
Funkcja Java, 64 znaki.
Powinien także działać w C.
źródło
PHP, 46 bajtów
Wersje online
lub
źródło
substr
Jest niepotrzebne (-12 bajtów). Powinieneś wspomnieć, jak je uruchomić.-984802906
?<?=bindec(strrev(sprintf("%064b",$argn<<32)));
JS 115
Cóż, to wcale nie wygląda dobrze: D
Metoda @Florian F w JS ma długość 53 bajtów:
źródło
it may be a function
środki reguły nie trzeba wpisem lub wierszaC #
8174Operacje bitowe, które najprawdopodobniej można wykonać krócej we wszystkich językach programowania.
Zasadniczo, przełóż wszystkie moce od 2 do maksymalnej liczby całkowitej + 1 (co zamienia się w potęgę dwóch), a ponieważ (2 147 483 647 + 1) = 0 mogę zapętlić do 0. Przesunięcie bitu w lewo do prawa, aby przenieść bit do pierwszego pozycja. Ostatni bit na miejscu 32 idzie w 31 krokach w prawo, drugi ostatni idzie w 30, itd. Tak więc używając operatora AND z 1, będę wiedział, czy jest to 1 lub 0. Jeśli to 1, dodam bieżącą wartość i do wyniku i zwróc to.
źródło
i
kiedy je deklarujesz, i zapisać bajt, usuwająci++
z pętli for, i zamiast porównywać wynik1&...
z 0, możesz całkowicie usunąć instrukcję if i pomnożyći
przez wynikr|=i*(1&(V>>(31-l++)));
C # 142
Rozszerzony
źródło
Python - 37
Podobne do rozwiązania @ isaacg.
źródło
C ++, 160
To nie jest najkrótszy, ale wykorzystuje tylko 24 operacje.
Zaczerpnięte z książki Hacker's Delight.
Gra w golfa:
Nie golfowany:
źródło
Haskell, 145 - bez operacji bitowych
Wirowanie bitów wydaje mi się antytezą Haskella, więc uniknąłem użycia operatorów bitowych. Powstały program z pewnością nie jest najkrótszym uczestnikiem, ale pomyślałem, że użycie matematyki zamiast kręcenia bitów było co najmniej interesujące.
Wyjaśnienie
0
s i1
s, najpierw najmniej znaczący bit, wielokrotnie dzieląc przez 2 i biorąc resztę0
s z końcem tej listy0
i1
na liczbę całkowitą, zakładając, że najbardziej znaczący bit jest pierwszy (powtarzane podwójne i dodawanie).Nie jestem do końca pewien, co stanowi „standardową bibliotekę” w Haskell, więc założyłem, że Data.Tuple i Data.List są w porządku (są dość standardowe).
Ponadto, wyjście jest 32-bitową liczbą całkowitą bez znaku, ponieważ zmiana, która kosztowałaby mnie bajty: argumentuję to pod „pominięciami to darmowa gra”.
źródło
PHP,
4641 bajtówwypróbuj je online
bitowe ... mniej więcej. Uruchom jako potok z
php -nR '<code>'
.PHP, 46 bajtów
czyste rozwiązanie bitowe; uruchomić jako potok z
-nR
.PHP,
4759 bajtówinne wbudowane podejście; zapisz do pliku i uruchom jako potok za pomocą
-F
.źródło
Perl - 60
+1 za flagę p (daj mi znać, jeśli liczę to źle).
Biegnij z:
źródło
C ++ 69
źródło
e;i;
? Deklaracje bez typu nie są poprawnym językiem C ++. W przypadku zmiennych nie jest to nawet ważne C.int r(int n){int e=0,i=0;for(;i<32;)e=e*2|1&n>>i++;return e;}
61 bajtów :)R, 45
Przykłady:
Zawsze nieśmiała od odpowiedzi w Pythonie. To cholerne słowo kluczowe funkcji.
źródło
Rubin,
4341 bajtówdef r(n)(0..31).inject(0){|a,b|a*2+n[b]}end
W Ruby użycie notacji indeksu nawiasów (foo [i]) zwraca bit na n-tym miejscu.
--Edytować--
Refaktoryzacja
inject
funkcjonalności zabiera kilka bajtówdef r(n)z=0;32.times{|i|z=z*2+n[i]};z;end
źródło
Perl5: 46
Nic fajnego. Przesuwa wyjście w lewo, kopiuje lsb przed przesunięciem źródła w prawo.
źródło
Clojure,
202156142źródło
Perl (37 + 1)
w zasadzie port rozwiązania C autorstwa Todda Lehmana
perl -E '$t=<>;map$r=2*$r|1&$t>>$_,0..31;say$r'
źródło