Najpierw wyjaśnienie:
Gdy s = 4 (to znaczy, że moduł jest równy 0xF) uzyskać następujące odwijania:
m = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
m = ((n >> 16) + (n & 0x0000FFFF)
m = ((n >> 8) + (n & 0x000000FF)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = m == 0xF ? 0 : m;
To różni się od tego, co masz w swoim pytaniu. Aby wyjaśnić, dlaczego to działa:
Słyszeliście o sztuczce matematycznej, w której jeśli doda się wszystkie cyfry numeru i będzie podzielna przez 9, to pierwotny numer też jest? To działa, ponieważ resztki dzielenia zarówno oryginału, jak i sumy przez 9 są takie same. Właściwie to właśnie tutaj robimy, tylko w innej bazie - w twoim przykładzie z bazą szesnastkową.
Matematyka kung-fu jest taka:
Wkład każdego cyfrą szesnastkową do końcowej wartości mogą być reprezentowane V * 16^P. Zauważ, że 16^P = 1 (mod 15), więc każdy wkład w postaci heksadecymalnej cyfry do wartości końcowej jest po prostu V (mod 15). Innymi słowy, aby uzyskać całkowity wkład wszystkich cyfr, dodaj je wszystkie do (mod 15).
Operacje bitowe są po prostu sprytnym sposobem robienia tego w logarytmicznej liczbie kroków: wielokrotnie dodawaj pierwszą połowę cyfr szesnastkowych do drugiej połowy.
Problem z trikiem 9-krotnie polega na tym, że możesz otrzymać dwucyfrowy numer: 99 = 9 + 9 = 18 (mod 10)! Potem znowu załatwiaj sprawę: 18 = 1 + 8 = 9 (mod 10).
Podobnie postępujemy z "dodatkowymi" iteracjami m = ((n >> 4) + (n & 0x0000000F), dopóki pozostała liczba nie przekroczy jednej cyfry.
Teraz jedynym pozostałym szczegółem jest, jeśli otrzymamy 0xF jako wynik, w którym przypadku chcemy zamiast tego 0x0.
Tak, wiedziałem o tym. Pracuję nad optymalizacją metody modulowania zespołu, która w tej chwili wykorzystuje gałęzie i maskę formularza 2^n-1. Próbuję więc pozbyć się gałęzi i zamiast tego użyć tej metody. –
Interesujące. Czy mogę zapytać, jaki rodzaj aplikacji używasz modułu 2^n-1? Czy jest jakiś powód, aby nie używać 2^n lub liczby pierwszej? – JS1
@ JS1 To nie jest takie niezwykłe. Jeden z wielu przykładów: bajtowy kod Reeda-Solomona (rozpoznawanie i korygowanie błędów danych) i ogólnie algorytmy oparte na polu Galois. Kodowanie (z RS) jest wróżka prosta w kodzie, składa się głównie z pętli, dodatków i modulo (biorąc pod uwagę, że niektóre statyczne dane są obliczane z góry, zamiast za każdym razem podczas dekodowania) – deviantfan