Algorytmy obliczające, jeśli liczba jest wielokrotnością liczby 3

Wykonując rachunek psychiczny, możesz:

• Biorąc pod uwagę liczbę całkowitą k, zsumuj wszystkie cyfry (w podstawie 10), a jeśli wynikiem jest wielokrotność 3, to k jest wielokrotnością 3.

Czy znasz algorytm działający podobnie, ale działający na cyfrach binarnych (bitach)?

• Najpierw zastanawiałem się nad użyciem gotowych funkcji mojego języka konwertujących liczbę całkowitą na ascii, aby wykonać konwersję z bazy 2 na bazę 10, a następnie zastosować sztuczkę rachunku różniczkowego. Ale oczywiście mógłbym również samodzielnie zakodować konwersję podstawową 2 na 10. Jeszcze tego nie zrobiłem, ale spróbuję.

• Potem pomyślałem o podziale euklidesowym w bazie 2 ...

Zastanawiam się jednak, czy istnieją inne środki, algorytmy.

Rozważ następujące dwie uwagi (pozostawione czytelnikowi jako ćwiczenie):

1. Parzyste potęgi dwóch to 1 moduł 3.
2. Dziwne potęgi dwóch to -1 modulo 3.

Dochodzimy do wniosku, że liczba (binarnie) jest podzielna przez trzy wtedy i tylko wtedy, gdy suma bitów w pozycjach parzystych jest równa sumie bitów w pozycjach nieparzystych modulo 3.

Co z automatem skończonym dla zadania?

Oczywiście magia jest tylko obliczenie modulo 3. Dodanie symbolu ciąg za oznacza „wartość binarna” łańcucha idzie od dla do dla . W konsekwencji ze stanu i symbolu przechodzimy do stanu , dla i . Uwaga jest łańcuchem, wheras jest jego wartością jako ciąg binarny.x v a l ( x ) x 2 ⋅ v a l ( x ) + a x a p a 2 p + a mod 3 p ∈ { 0 , 1 , 2 } a ∈ { 0 , 1 } x ∈ { 0 , 1 } ∗ v a l ( x ) ∈ $a$$x$$val(x)$$x$$2\cdot val(x)+a$$xa$$p$$a$$2p+a \bmod 3$$p\in \{0,1,2\}$$a\in \{0,1\}$$x\in \{0,1\}^*$$val(x)\in \Bbb{N}$

W systemie dwójkowym liczby 1, 100, 10000 (= 100 × 100), 1000000 (= 100 × 100 × 100) itd. Dają tę samą resztę po podzieleniu przez 11 (trzy). Dlatego jeśli podzielimy liczbę binarną na części o parzystej długości , suma części daje taką samą resztę jak liczba pierwotna.

(Przy dzieleniu liczby dodajemy tyle zer, ile potrzeba na początku . Na przykład podzielilibyśmy 10111 na grupy 01,11 lub 0001,0111.)

Matematycznie, tylko podzielić liczbę na grupy dwóch cyfr, a następnie dodać do grupy; i powtarzaj to, aż wynik wyniesie 00 lub 11 = pierwotna liczba była wielokrotnością trzech; lub 01 lub 10 = pierwotny numer nie był wielokrotnością trzech.

W przypadku programu komputerowego użycie grup po osiem, szesnaście lub trzydzieści dwa bity może być szybsze dla twojego procesora. Na przykład, jeśli dodawanie ośmiobitowe jest najszybsze, po prostu zrób sumę wszystkich bajtów i jeszcze raz, aż wynik zmieści się w jednym bajcie. Następnie użyj jednej instrukcji, aby określić pozostałość po podzieleniu przez trzy.

(Uwaga: zakładamy tutaj liczby całkowite bez znaku . Przy podpisanym numerze wymaga nieco więcej uwagi. Na przykład 129 to wielokrotność 3, ale -127 nie, chociaż bity 10000001 oznaczają dla byłego jako bajt niepodpisany i ten ostatni jako bajt podpisany).

Powtarzane odejmowanie, choć nie jest specyficzne dla danych binarnych, zawsze stanowi pewny sposób na obliczenie dzielenia z resztą (a zatem, jeśli liczba jest wielokrotnością liczby 3).