07 lipca 2015

Dodawanie z pomocą logiki

Swego czasu w czerwcu 2015 roku opublikowałem posta o tytule: "Operatory arytmetyczne wyrażone operatorami logicznymi".

Niedawno spróbowałem dodawać następującą metodą rekursywną: 
przechodząc po cyfrach argumentów, przy generowaniu kolejnej sumy biorę mniejszą z nich dla pierwszego argumentu a, zaś moduł różnicy cyfr jako argument drugiej b. Suma docelowa jest równa 2a+b. 
Np. 4283 + 1728 = 1223 * 2 + 3565
bo np. min(4,1)=1, 4-1=3 na pozycji tysięcy itd. Na pozycji jedności jest min(3,8)=3, 8-3=5. 

Sposób ten czasem się zapętla, lecz jest proste rozwiązanie. Przekształcam b=2*c+e, gdzie e jest zerem lub jedynką w zależności od parzystości b, oraz do dalszych przekształceń stosuję a+c, wartość zmniejszona co najmniej dwukrotnie.
4283 + 2728 = (1223*2 + 3564)+1 = (1223+1782)*2+1
Tym razem zapętlenie nie występuje. 

Metoda działa też w innych systemach liczbowych. Zaś w binarnym sprowadza się do opublikowanego w czerwcu algorytmu. 
Jest coś więcej. Algorytm ten wyznacza w jednej iteracji bit najmniej znaczący oraz z dużą dokładnością bit najbardziej znaczący. Chodzi o ten na pozycji, do której występuje przeniesienie przy zmianie długości liczby. Nazwę maską wartość, w niej tylko skrajne bity mają znaczenie.
Kiedy następuje podsumowanie - dodawanie można zastąpić OR-owaniem. 

Przykład: 15+9 = 1111b + 1001b
pierwsza iteracja: a=1001b, b=0110b, do dalszej części przechodzą 
(1001b+11b)*2 + 0
które przekształcamy do (001b+11b)*2 + 10000b (b jest parzyste, bit najmniej znaczący jest równy 0)
druga iteracja: a = 1, b=10b, 
po przekształceniu: (1+1), maska 0000
trzecia iteracja: a=1, b=0, tu wyznaczenie 2a = 10 jest tak duże, że zahacza o wyznaczony już bit maski w poprzedniej iteracji.
Podsumowanie, czyli orowanie wartości 10000b | 0000<<1 | 10<<2 = 11000b  = 24
jest to wartość 15+9 = 24. 

Inny przykład: 15+7, już szybciej. 1111b + 111b
a = 111b, b = 1000b, maska 00000b
suma 111b + 100b 
a = 100b, b = 11b, maska 1001b, bit najbardziej znaczący pobrany z 2a = 1000b
suma 0+1 = 1, kończymy wartością 01, co dajemy jako maskę.
Podsumowanie: 00000 | 10010 | 0100 = 10110b

Są 3 iteracje w porównaniu z przechodzeniem 4 razy po bitach. Wszystkie przechodzenia można traktować równocześnie jedną operacją logiczną.