Comment vérifier si un nombre est un multiple de 6?

Question

Je voudrais un alogrithm qui utiliserait seulement des opérations de décalage, ajouter ou soustraire pour trouver si un nombre est un multiple de 6. Donc, fondamentalement juste des opérations binaires. Jusqu'ici, je pense que je devrais logiquement déplacer le nombre deux fois pour diviser par 4 et ensuite soustraire 6 une fois. Mais je sais que quelque chose ne va pas avec mon approche et je n'arrive pas à comprendre quoi.

Answer 1

diriez-vous de garder en soustrayant le nombre de 6 jusqu'à ce que il atteint zéro. Si vous obtenez zéro le nombre est divisible par 6 sinon, non. OU continuez à diviser le nombre par 2 (opération de décalage sur binaire) jusqu'à ce que le nombre soit inférieur à 12. puis soustrayez 6 de ce nombre. Si inférieur à zéro (non divisible) si zéro divisible. si elle n'est pas soustraite 3 Si inférieur à zéro (non divisible) si zéro divisible.

Answer 2

Reference: http://wiki.answers.com/Q/How_can_you_tell_if_a_number_is_a_multiple_of_6 

It is a multiple of six if BOTH of the following statements are true: 
1) The last digit (ones place) is 0, 2, 4, 6, or 8. 
2) When you add all the digits together, you get a multiple of 3. 


Reference: http://wiki.answers.com/Q/How_can_you_tell_if_a_number_is_a_multiple_of_3 

1) Start with a number N. 
2) Sum the digits of the number, and get M. 
3) If M is larger than 10, set N=M and return to stage 2. 
4) Otherwise, M is now smaller than 10. If M is 0,3,6 or 9, then N is a multiple of 3 

Answer 3

Vous pourriez essayer d'implémenter un algorithme de division avec les opérations primitives disponibles. L'algorithme long division de base de la 4e année pourrait être assez (juste faire les choses dans la base 2 au lieu de la base 10, au lieu de la multiplication opérateurs de bits)

Answer 4

1) Simple (N & 1) == 0 pour vérifier si le nombre est divisible par 2.

2) Utilisez la réponse Bit bidouille (du fil This.) pour vérifier la divisibilité par 3.

Si les deux sont vrais, votre nombre est divisible par 6.

Answer 5

OK. Voici comment je vais y aller (juste une première pensée):

Un multiple de 6 est à la fois un multiple de 2 et 3, il devrait donc satisfaire les critères de divisibilité de 2 et 3 en même temps ... Alors ...

• Vérifiez divisibilité par 2:

  1. décalage vers la droite le nombre
  2. Si reste> 1, répéter 1.

  3. Si reste = 1, alors FALSE, sinon continuez.

     La vérification de la divisibilité par 2, pourrait évidemment être également mise en œuvre par (N & 1 == 0), comme indiqué ci-dessus. Cela permet de vérifier simplement le dernier chiffre de la représentation binaire de N: si elle est 1, N est impair (donc pas divisible par 2), si elle est 0, il est parfaitement divisible ...

• Vérifier divisibilité par 3 :
  1. Soustraire 3.
  2. Si reste> 3, répéter 1.
  3. Si reste> 0, FALSE, sinon TRUE.

Answer 6

Si nous étendons la gamme des opérations à "bit-masquage" et "bit-shifting", il est simple.

Comme certains l'ont dit, la divisibilité par deux est équivalente à (n & 1) == 0. La divisibilité par 3 est (relativement) facile en binaire. Initialiser un accumulateur a à 0, puis répéter a += (n & 3); n = (n >> 2); jusqu'à ce que n soit 0. Si (et seulement si) a est 3 est n divisible par 3.