Jak sprawdzić, czy liczba binarna dzieli się przez 3?

Question

Chcę wiedzieć, czy jest jakiś podzielna reguła w systemie binarnym na podzielenie przez 3.

Na przykład: w systemie dziesiętnym, jeżeli suma cyfr dzieli się przez 3, a następnie numer podzielona jest przez 3. Dla exmaple: 15 -> 1+5 = 6 -> 6 jest podzielone przez 3, więc 15 jest podzielone przez 3.

Ważne jest, aby zrozumieć, że nie szukam KODU, który to zrobi .. bool flag = (i% 3 == 0); nie jest odpowiedzią, której szukam. Szukam czegoś, co jest łatwe do zrobienia, tak jak prawo dziesiętne.

Answer 1

Patrz tej stronie: How to Tell if a Binary Number is Divisible by Three

Zasadniczo policzyć liczbę niezerowych pozycji nieparzystych bitów i niezerowej pozycjach parzystych bije z prawej. Jeżeli ich różnica jest podzielna przez 3, a ta liczba jest podzielna przez 3

Na przykład:

15 = 1111 który ma nieparzystą 2 i 2, również bez bitów zerowych. Różnica wynosi 0. Tak więc 15 jest podzielna przez 3.

185 = 10111001 który ma 2 nieparzyste bity niezerowe i 3 równe bity niezerowe. Różnica wynosi 1. Tak więc 185 nie jest podzielna przez 3.

Wyjaśnienie

Rozważmy wartości 2^n. Wiemy, że 2^0 = 1 jest przystający 1 mod 3. Tak więc 2^1 = 2 jest konwentem 2*1 = 2 mod 3. Kontynuując wzorzec, zauważamy, że dla 2^n, gdzie n jest nieparzyste, 2^n jest przystające 1 mod 3 i nawet jeśli jest zgodne, 2 mod 3, które jest -1 mod 3. Tak więc 10111001 jest zgodny z 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3, który jest przystający do 1 mod 3. W związku z tym 185 nie jest podzielne przez 3.