Wyzwanie
Zaimplementuj funkcję, która akceptuje dwie liczby całkowite, których wartości mieszczą się w zakresie od 0 do 255 i zwraca sumę tych liczb całkowitych mod 256. Możesz używać tylko negacji bitowej (~), bitowej lub (|), operatorów przesunięcia bitów (>>, <<) i przypisanie (=).
Do rzeczy, których nie można użyć, należą (ale nie wyłącznie)
- Dodawanie, odejmowanie, mnożenie i dzielenie
- Pętle
- Instrukcje warunkowe
- Wywołania funkcji
Wygrywa niewiele zastosowań binarnych lub binarnych negacji i operacji przesunięcia bitów . W przypadku remisu wygrywa najpopularniejsze rozwiązanie. Jak zawsze obowiązują standardowe luki .
Oto przykład prostego 2-bitowego sumatora. Wykorzystuje 77 binarnych negacji, 28 binarnych orów i 2 przesunięcia bitów, co daje łączny wynik 107 (można to zobaczyć po uruchomieniu preprocesora C gcc -E
). Można to uczynić znacznie bardziej wydajnym, usuwając #define
s i upraszczając powstałe wyrażenia, ale zostawiłem je dla jasności.
#include <stdio.h>
#define and(a, b) (~((~a)|(~b)))
#define xor(a, b) (and(~a,b) | and(a,~b))
int adder(int a, int b)
{
int x, carry;
x = xor(and(a, 1), and(b, 1));
carry = and(and(a, 1), and(b, 1));
carry = xor(xor(and(a, 2), and(b, 2)), (carry << 1));
x = x | carry;
return x;
}
int main(int argc, char **argv)
{
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (adder(i, j) != (i + j) % 4) {
printf("Failed on %d + %d = %d\n", i, j, adder(i, j));
}
}
}
}
Aktualizacja: Dodano przykład i zmieniono kryteria punktacji
źródło
Odpowiedzi:
Python, 36 operacji
Metody logarytmiczne w parametrze „8”!
Chodzi o to, aby dowiedzieć się, które wskaźniki przepełniają się i powodują przeniesienie. Początkowo jest to po prostu miejsca, gdzie obie
a
anddb
mają1
. Ale ponieważ przenoszone bity mogą powodować dalsze przelania, należy to ustalić iteracyjnie.Zamiast przepełniać każdy indeks do następnego, przyspieszamy ten proces, przesuwając 1 indeks, następnie 2 indeksy, a następnie 4 indeksy, pamiętając o miejscach, w których nastąpiło przepełnienie (H) i gdzie przepełnienie nie może się już zdarzyć (K ).
Prostsze iteracyjne rozwiązanie z 47 operacjami:
Stanowisko testowe dla każdego, kto chce go skopiować.
źródło
C - 0
Używa operatorów spoza ~, |, >>, << i =, ale widzę rozwiązania wykorzystujące operatory rzutowania i przecinków, więc myślę, że reguła nie jest zbyt surowa, pod warunkiem, że nie używa zabronionych operatorów.
źródło
python, wynik =
8380Rozwiń pętlę. To 10 operacji na pętlę razy 7 pętli, 7 dla ostatniego xora i 3, aby zgnieść 9. bit na końcu.
Realizuje równanie
x+y = x^y + 2*(x&y)
, powtarzając je 8 razy. Za każdym razem na dole jest jeszcze jeden bit zeroy
.źródło
C, wynik:
7760Grał w golfa na cholerę,
206169131 bajtów:Rozszerzony:
Zasadniczo to samo rozwiązanie (matematycznie), które
wymyślił @KeithRandall@JuanICarrano, ale korzysta ze zdolności C do szybkiego i swobodnego grania ze zmiennymi typami i wskaźnikami, aby wyczyścić wszystko po pierwszych 8 bitach bez użycia więcej operatorów.Zależy od endianowości maszyny oraz sizeof () int i char, ale powinien być w stanie być przeniesiony do większości aplikacji specyficznych dla maszyny z odpowiednią matematyką wskaźnika.
EDYCJA: Jest to wyzwanie, w którym C (lub inne języki niskiego poziomu) będą miały wyraźną przewagę - chyba że ktoś wymyśli algorytm, którego nie trzeba nosić.
źródło
unsigned char
. Jest czystszy i bardziej przenośny.unsigned
nie przychodzi mi naturalnie w golfie kodowym. Oczywiście masz rację - zaktualizowano.Python - wynik
6664Jest to równanie sumatora tętnienia. C jest nosicielem. Jest obliczany jeden bit na raz: w każdej iteracji przeniesienie jest propagowane w lewo. Jak wskazał @Orby, oryginalna wersja nie zawierała dodatku modułowego. Naprawiłem to i zapisałem cykl w iteracji, ponieważ pierwsze przeniesienie jest zawsze równe zero.
źródło
s(255,2)
Zwraca257
raczej niż1
). Możesz to poprawić, zmieniając ostatnią linię, doreturn ~(~xxor(axb,C)|256)
której dodaje się 3 punkty.C ++ - wynik: 113
źródło
add(1, 255)
zwraca 128 dla mnie, @Ryan.%
nie znajduje się na liście dozwolonych operatorów, a mianowicie~
,|
,>>
, i<<
. Może zastąpisz toands(x8|y8, 255)>>1
?~(~x8 | y8 | 0xFFFFFF00)
zrobiłby to dobrze, mając tylko 4+ swojego wyniku.byte
nieint
spowodowałoby automatycznego przepełnienia?