Je dois écrire une certaine logique pour déterminer, étant donné un nombre pair. La plus haute puissance de deux qui la divise uniformément. Quelle est la valeur maximale de 2 ^ N où l'entrée% 2 ^ n == 0?
IE:
Entrée -> Sortie P>
4 (0100) -> 4 8 (1000) -> 8 12 (1100) -> 4 14 (1110) -> 2 24 (11000) -> 8 etc....
4 Réponses :
sans utiliser de point flottant arithmétique:
((x ^ (x - 1)) >> 1) + 1
X = 24 (24 ^ 23) = 24623 24623 >> 1 = 12311 12311 + 1 = 12312 ai-je calculé quelque chose de mal?
Jonathan: ^ est xor, donc (24 ^ 23) est 15.
BTW, si x n'est pas signé, je crois que le seul cas de bord qui nécessite une manipulation spéciale est nul.
Si vous êtes prêt à assumer le complément d'arithmétique de 2:
Si vous faites beaucoup de ce genre de chose (ou même si vous ne trouvez que de la trouver intéressant), trouvez-vous une copie du livre "Delight de Hacker's".
edit: Avakar note correctement que cela ne dépend pas du complément de 2 de 2 si le type est non signé. La section correspondante de la norme est §6.2.5, paragraphe 9:
Un calcul impliquant non signé
les opérandes ne peuvent jamais déborder, car un
résultat qui ne peut être représenté par
Le type d'entier non signé résultant est
Modulo réduit le nombre qui est un
plus grande que la plus grande valeur que
peut être représenté par le résultat résultant
Tapez.
"Un plus grand que la plus grande valeur" laisse une certaine salle de guérison pour une mise en œuvre particulièrement pervers (en particulier, une implémentation qui n'utilise pas de binaire, par exemple), mais que vous êtes peu probable de la rencontre. x & -x
+1. Pour le compte rendu, vous n'avez pas à assumer le complément de 2. Cela fonctionnera vers n'importe quelle architecture, tant que X est de type arithmétique non signé.
Disons que nous avons un type de 32 bits avec un complément de 1 € d'arithmétique: si x est 1, alors -x est 0xfffffffe et x & -x est 0, ce qui n'est pas la réponse que le questionneur veut. En tant que j.f. Sebastian Notes, vous peut Travailler à ce sujet en utilisant X & (~ x + 1) , qui n'est que la négation de compliment de 2 en deux opérations.
(~ x + 1) est la négation de deux compléments, c'est-à-dire.
Non. Pour x non signé, -x sera 2 ^ k-x pour certains k . Dans votre exemple, k sera 32 et -x sera 0xffffffff . Encore une fois, non signé est la clé ici, tous les paris sont éteints pour signé x .
Nous pouvons remplacer Bit de bits bas Vous devez absolument savoir fournit une explication détaillée. < / p> (- x) par (~ x + 1) :
Notez que (~ x + 1) est la définition de -x dans le complément de 2. Cela fait de cela une réponse légèrement meilleure que X & (-X), puisque (~ x + 1) ne dépend que de la machine à l'aide de l'arithmétique binaire droite, qui est à peu près une donnée ces jours-ci (mais pas toujours!).
Un nombre dans le formulaire 2 ^ N est écrit en binaire par un 1 suivi d'une série de 0 ou plus 0s. Par exemple, 1, 10, 100, 1000, ... etc. sont tout le pouvoir de 2.
Pour obtenir la puissance la plus élevée de 2 qui divise un nombre donné, vous pouvez effectuer les deux étapes suivantes:
Écrivez le numéro sous forme binaire. Par exemple, si le nombre est 168, écrivez 10101000.
frappe tous les bits avant le premier bit du côté droit qui contient 1. Dans le cas de 168, ce qui reste de 1000 (= 8 en décimal) après avoir frappé la première partie de 10101000.
Ce qui reste est votre résultat - c'est-à-dire une puissance la plus élevée de 2 qui divise le nombre.
Programmatiquement, let x est votre numéro d'entrée. Ensuite, votre sortie souhaitée sera la suivante: Explication:
x - (x ^ (x-1))
x ^ (x-1) [signification x xor x-1] se débarrasse du premier 1 du côté du LSB (bit le moins significatif)
x - (x-x-1)) se débarrasse de la pièce restante et conserve seulement le premier premier du côté LSB.