Je travaille sur un moyen de diviser un entier signé par une puissance de 2 en utilisant uniquement des opérateurs binaires (<< >> + ^ ~ & |!), et le résultat doit être rond vers 0. Je suis tombé à travers Cette question également sur Stackoverflow sur le problème, cependant, je ne peut pas comprendre pourquoi ça marche. Voici la solution: Je comprends la pièce x >> 31 (ajouter uniquement la partie suivante si x est négatif, car si C'est positif x sera automatiquement arrondi vers 0). Mais ce qui me dérange est le (1 << n) + ~ 0 partie. Comment cela peut-il fonctionner?
3 Réponses :
Ceci est "Code en écriture uniquement": Au lieu d'essayer de comprendre le code, essayez de le créer par vous-même.
Par exemple, divisons un nombre par 8 (décalage à droite par 3).
Si le nombre est négatif, le passage à droite normal dans la mauvaise direction. "Corrigez-le" en ajoutant un numéro: p> ici, vous pouvez proposer une formule mathématique pour Comment unifier les deux cas? Vous devez faire une expression qui ressemble à ceci: p> où quel que soit code> ou faire un essai et une erreur . Quoi qu'il en soit, ici peu importe tout = 7 code>: p> true code> est 7 pour négatif x code> et 0 pour positif x code>. L'astuce ici utilise ici x >> 31 code>, qui est un nombre de 32 bits dont les bits sont égaux à la signification de x code>: tous 0 ou tous 1. SO Stuff Code> est P> (x >> 31) & 7
Étant donné que x est de type int , (x >> 31) peut ou peut ne pas résulter dans tous les 1s lorsque x est négatif. Les états standards ISO C (par exemple la section 6.5.7.7, paragraphe 5) qui évacuant un entier signé de valeur négative invoque comportement défini par la mise en œuvre .
Le comportement défini de la mise en œuvre peut être corrigé par la coulée à un non signé, ainsi que cette solution se casse si elle passe de 0.
Référence de OP est d'un code en particulier restreindre le code à utiliser uniquement des opérateurs "binaires" code OP échoue lorsque C # de code> et de nombreuses différences subtiles qui le causent le code Bad em> avec C, car ce message est étiqueté. INT code> n'est pas nécessairement 32 bits, donc à l'aide d'un nombre magique de 32 ne fait pas une solution robuste. p> (1 Résultats dans la mise en œuvre Comportement défini lorsque N CODE> provoque un bit à décaler dans le lieu de connexion. Pas bon codage. P> > + ^ ~ & | ! code> encourage un codeur à supposer em> choses sur int code> qui n'est pas portable ni compatible avec la spécification C. Donc, le code posté par OP ne "fonctionne pas" en général, bien que peut fonctionner dans de nombreuses implémentations communes. P> int code> n'est pas le complément de 2, pas utilise la plage [- 2147483648 Une alternative simple, en supposant long LONG code> dépasse la plage de int code> suit. Je doute que cela me rencontre quelques-uns em> le coin des objectifs de l'OP, mais les objectifs donnés par OP encourage le codage non robuste. P> int divideByPowerOf2(int x, int n) {
long long ill = x;
if (x < 0) ill = -ill;
while (n--) ill >>= 1;
if (x < 0) ill = -ill;
return (int) ill;
}
En supposant que 2-complément, il suffit de changer le dividende équivalent à un certain type de division: non pas la division conventionnelle où nous nous arrondirons le dividende au prochain multiple de diviseur vers zéro. Mais un autre genre où nous sommes autour du dividende vers l'infini négatif. J'ai redécouvert que dans Smalltalk, voir http: // smallissimo.blogspot.fr/2015/03/is-bbbshift-equivalent-a-division-in.html .
Par exemple, divisons -126 par 8. Traditionnellement, nous écririons p>
1000|0010 >> 3 = 1111|0000 1000|0010 = 1111|0000 * 0000|1000 + 0000|0010
complément à deux. Mais vous avez raison, la réponse n'explique rien. Maintenant, vous obtenez des bowvotes quand vous le faites ...
x + ~ 0 est un moyen amusant d'écrirex - 1 , il est juste de tronquer que le masque d'arrondi àn bits1) Préoccupé par la division des nombres négatifs? 2) préoccupé par la division des nombres négatifs de manière publiée? 3) Préoccupé par la manutention
x == int_min ? 4) Qu'en est-il des pouvoirs de 2 qui répondent / dépassent la largeur du bit deint ? Sinon, le but est si étroit que ce n'est pas si utile au-delà d'une idée étroite de la possibilité ou de la plage et des détails deint .