algorithm - sistema - ¿Cómo saber si un número binario se divide por 3?

sistema octal

Question

Quiero saber si hay alguna regla divisible en el sistema binario para dividir por 3.

Por ejemplo: en decimal, si la suma de dígitos está dividida por 3, entonces el número se divide por 3. Por ejemplo: 15 -> 1+5 = 6 -> 6 está dividido por 3, por lo que 15 se divide por 3.

Lo importante de entender es que no estoy buscando un CÓDIGO que lo haga ... bool flag = (i% 3 == 0); no es la respuesta que estoy buscando. Busco algo que a los humanos les resulte fácil hacer exactamente como la ley decimal.

Answer 1

Consulte este sitio web: Cómo saber si un número binario es divisible por tres

Básicamente, cuente el número de bits de posiciones impares diferentes de cero y bits de posición pares distintos de cero de la derecha . Si su diferencia es divisible por 3, entonces el número es divisible por 3.

Por ejemplo:

15 = 1111 que tiene 2 bits impares y 2 bits no nulos. La diferencia es 0. Por lo tanto, 15 es divisible por 3 .

185 = 10111001 que tiene 2 bits impares distintos de cero y 3 bits incluso distintos de cero. La diferencia es 1. Por lo tanto, 185 no es divisible por 3 .

Explicación

Considere los 2^n valores. Sabemos que 2^0 = 1 es congruente 1 mod 3 . Así 2^1 = 2 es congurent 2*1 = 2 mod 3. Continuando con el patrón, notamos que para 2^n donde n es impar, 2^n es congruente 1 mod 3 y para incluso es congruente 2 mod 3 que es -1 mod 3 . Por 10111001 tanto, 10111001 es congruente 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3 que es congruente 1 mod 3 . Por lo tanto, 185 no es divisible por 3.