Zestaw x86, 9 bajtów (na konkurencyjny wpis)
Wszyscy, którzy podejmują to wyzwanie w językach wysokiego poziomu, tracą prawdziwą frajdę z manipulowania surowymi bitami. Jest tak wiele subtelnych odmian sposobów na zrobienie tego, jest to szalone - i dużo zabawy o tym myśleć. Oto kilka rozwiązań, które opracowałem w 32-bitowym języku asemblera x86.
Z góry przepraszam, że nie jest to typowa odpowiedź na golfa. Będę dużo gadać na temat procesu iteracyjnej optymalizacji (dla rozmiaru). Mam nadzieję, że jest to interesujące i edukacyjne dla większej grupy odbiorców, ale jeśli jesteś typem TL; DR, nie obrażę się, jeśli przejdziesz do końca.
Oczywistym i wydajnym rozwiązaniem jest sprawdzenie, czy wartość jest nieparzysta, czy parzysta (co można zrobić skutecznie, patrząc na najmniej znaczący bit), a następnie odpowiednio wybrać pomiędzy n + 1 lub n-1 . Zakładając, że dane wejściowe są przekazywane jako parametr w ECXrejestrze, a wynik jest zwracany w EAXrejestrze, otrzymujemy następującą funkcję:
F6 C1 01 | test cl, 1 ; test last bit to see if odd or even
8D 41 01 | lea eax, DWORD PTR [ecx + 1] ; set EAX to n+1 (without clobbering flags)
8D 49 FF | lea ecx, DWORD PTR [ecx - 1] ; set ECX to n-1 (without clobbering flags)
0F 44 C1 | cmovz eax, ecx ; move in different result if input was even
C3 | ret
(13 bajtów)
Ale do celów gry w golfa LEAinstrukcje te nie są świetne, ponieważ kodowanie zajmuje 3 bajty. Prosta DECwersja ECXbyłaby znacznie krótsza (tylko jeden bajt), ale wpływa to na flagi, więc musimy być nieco sprytni w sposobie rozmieszczania kodu. Możemy wykonać ubytek pierwszy i parzyste / nieparzyste Test sekund , ale potem musimy odwrócić wynik testu parzyste / nieparzyste.
Możemy również zmienić instrukcję warunkowego przeniesienia na gałąź, co może spowodować, że kod będzie działał wolniej (w zależności od przewidywalności gałęzi - jeśli dane wejściowe zmieniają się niekonsekwentnie między nieparzystymi i parzystymi, gałąź będzie wolniejsza; jeśli istnieje wzór, będzie szybciej), co pozwoli nam zaoszczędzić kolejny bajt.
W rzeczywistości dzięki tej zmianie cała operacja może być wykonana w miejscu, przy użyciu tylko jednego rejestru. Jest to świetne, jeśli wstawiasz gdzieś ten kod (i są szanse, że tak, ponieważ jest tak krótki).
48 | dec eax ; decrement first
A8 01 | test al, 1 ; test last bit to see if odd or even
75 02 | jnz InputWasEven ; (decrement means test result is inverted)
40 | inc eax ; undo the decrement...
40 | inc eax ; ...and add 1
InputWasEven: ; (two 1-byte INCs are shorter than one 3-byte ADD with 2)
(wstawiany: 7 bajtów; jako funkcja: 10 bajtów)
Ale co, jeśli chcesz, aby była to funkcja? Żadna standardowa konwencja wywoływania nie używa tego samego rejestru do przekazywania parametrów, jak ma to miejsce w przypadku wartości zwracanej, dlatego konieczne byłoby dodanie MOVinstrukcji rejestru-rejestru na początku lub na końcu funkcji. To nie ma praktycznie żadnego kosztu prędkości, ale dodaje 2 bajty. ( RETInstrukcja dodaje również bajt i istnieje pewien narzut związany z koniecznością wykonania i powrotu z wywołania funkcji, co oznacza, że jest to jeden z przykładów, w którym wstawianie daje korzyści zarówno prędkości, jak i wielkości, a nie tylko klasyczną prędkość - dla kompromisu przestrzeni.) W sumie, napisany jako funkcja, ten kod rośnie do 10 bajtów.
Co jeszcze możemy zrobić w 10 bajtach? Jeśli zależy nam w ogóle na wydajności (przynajmniej przewidywalnej wydajności), dobrze byłoby pozbyć się tej gałęzi. Oto bez rozgałęziające, zmieniające się w bitach rozwiązanie, które ma ten sam rozmiar w bajtach. Podstawowa zasada jest prosta: używamy bitowego XOR, aby odwrócić ostatni bit, konwertując wartość nieparzystą na parzystą i odwrotnie. Ale jest jeden problem - dla nieparzystych danych wejściowych, który daje nam n-1 , podczas gdy dla parzystych danych wejściowych daje nam n + 1 - dokładnie przeciwnie do tego, czego chcemy. Aby to naprawić, wykonujemy operację na wartości ujemnej, skutecznie odwracając znak.
8B C1 | mov eax, ecx ; copy parameter (ECX) to return register (EAX)
|
F7 D8 | neg eax ; two's-complement negation
83 F0 01 | xor eax, 1 ; XOR last bit to invert odd/even
F7 D8 | neg eax ; two's-complement negation
|
C3 | ret ; return from function
(wstawiany: 7 bajtów; jako funkcja: 10 bajtów)
Całkiem zręczny; trudno jest zrozumieć, jak można to poprawić. Jedno rzuca się w oczy: te dwie 2-bajtowe NEGinstrukcje. Szczerze mówiąc, dwa bajty wydają się być o jeden bajt za dużo, by zakodować prostą negację, ale to zestaw instrukcji, z którymi musimy pracować. Czy są jakieś obejścia? Pewnie! Jeśli otrzymamy XOR-2, możemy zamienić drugą NEGację na INCrement:
8B C1 | mov eax, ecx
|
F7 D8 | neg eax
83 F0 FE | xor eax, -2
40 | inc eax
|
C3 | ret
(wstawiany: 6 bajtów; jako funkcja: 9 bajtów)
Inną osobliwością zestawu instrukcji x86 jest instrukcja uniwersalnaLEA , która może wykonać ruch rejestru-rejestru, dodanie rejestru-rejestru, przesunięcie przez stałą i skalowanie wszystkiego w jednej instrukcji!
8B C1 | mov eax, ecx
83 E0 01 | and eax, 1 ; set EAX to 1 if even, or 0 if odd
8D 44 41 FF | lea eax, DWORD PTR [ecx + eax*2 - 1]
C3 | ret
(10 bajtów)
ANDInstrukcja jest podobna do TESTinstrukcji używaliśmy wcześniej, że zarówno zrobić bitowe AND i ustawić odpowiednio flagi, ale ANDfaktycznie uaktualnia operand przeznaczenia. Następnie LEAinstrukcja skaluje to o 2, dodaje oryginalną wartość wejściową i zmniejsza o 1. Jeśli wartość wejściowa była nieparzysta, odejmuje to 1 (2 × 0 - 1 = -1); jeśli wartość wejściowa była parzysta, to dodaje 1 (2 × 1 - 1 = 1).
Jest to bardzo szybki i skuteczny sposób na napisanie kodu, ponieważ znaczną część wykonania można wykonać w interfejsie, ale nie kupuje nam to zbyt wiele bajtów, ponieważ tak wiele zajmuje kodowanie złożonego LEAinstrukcja. Ta wersja również nie działa tak dobrze dla celów wstawiania, ponieważ wymaga zachowania oryginalnej wartości wejściowej jako danych wejściowych LEAinstrukcji. Tak więc przy ostatniej próbie optymalizacji cofnęliśmy się, sugerując, że nadszedł czas, aby się zatrzymać.
Tak więc, dla końcowego konkurencyjnego wpisu, mamy 9-bajtową funkcję, która pobiera wartość wejściową do ECXrejestru (pół-standardowa konwencja wywoływania oparta na rejestrze na 32-bitowym x86) i zwraca wynik w EAXrejestrze (jak w przypadku wszystkie konwencje wywoływania x86):
SwapParity PROC
8B C1 mov eax, ecx
F7 D8 neg eax
83 F0 FE xor eax, -2
40 inc eax
C3 ret
SwapParity ENDP
Gotowy do montażu za pomocą MASM; zadzwoń z C jako:
extern int __fastcall SwapParity(int value); // MSVC
extern int __attribute__((fastcall)) SwapParity(int value); // GNU
