J'ai récemment demandé lors d'une interview, en utilisant des opérateurs Just Bit Shift, écrit du code qui vous dirait si un numéro est divisible par 8, apparemment, le code est très court - Est-ce que quelqu'un a une indice?
Remarque: Si vous n'êtes pas obligé d'utiliser des changements, vous testez les bits inférieurs n pour être tout zéro avec un masque comme x & 7 == 0 0 , ou plus généralement
x & ((1l << n) - 1) == 0 . Comment puis-je dire si un chiffre est un multiple de quatre utilisant uniquement l'opérateur logique et?
9 Réponses :
static boolean divisibleBy8(int num) {
return (number & 7) == 0;
}
Ceci n'utilise pas seulement des changements de bits
OK OK, n'était pas sûr de savoir combien a mis l'accent sur le "changement". Certaines personnes ont tendance à confondre les termes. Sur le côté plus, cela fonctionne et c'est la solution la plus rapide. ;-)
Comment signifie "bit shift" signifie autre chose?
Dans ce "bitwise", c'était en réalité signifié, tout simplement pas exprimé avec précision.
avec tout entier représenté en binaire Le reste de la division par n'importe quelle puissance de deux est simplement la valeur des bits d'ordre inférieur afin 0b11001110 code> divisé par 0b1000 code> a le reste 0B110 code>. Donc, afin de vérifier la divisibilité par 8, vous devez vérifier si les trois bits de commande bas sont tous zéro: if ((x << -3) != 0)
divisibleby8 = true;
N'est-ce pas "divisible par 4"?
Vous connaissez une réponse similaire à c'était dans ma tête, je n'ai pas mentionné mes pensées à ce sujet parce que je pensais que cela pourrait être faux, pourquoi est-ce que je me suis retrouvé ?? Laissez-moi confirmer ces œuvres
@godzilla parce que 1 << 3 == 8
2 à la puissance 3 est 8. Un nombre est divisible par huit si et uniquement si la valeur la plus basse, trois bits sont nulles.
@ Davidrodríguez-Dribesas - sûrement plus compact, mais incorrect ... (a vu votre édition -> toujours dépendante de la machine)
Merci Jack qui efface les choses, je vais me bloquer mes compétences de décalage, c'était une de ces questions qui auraient pu être un changeur de vie, mais pas cette fois, je serai prêt pour cela la prochaine fois que vous êtes :)
Hmm ... Cela s'appuie sur la comparaison de deux nombres et la comparaison de (i.e. Subvention) n'est pas une opération de décalage dans le sens littéral.
if(! (num << 29) ) { // assuming num is 32 bits
// num divisible by 8
}
@Peterlawrey question porte c balise, c'est valide C. Vous avez raison pour Java.
if (x == ((x >> 3) << 3))
en Java, sans savoir si le type est ceci changera de 29 ou 61 bits selon le cas pour ce type. Il ne sera vrai que si les trois bits inférieurs sont 0. long ou int Vous pouvez faire ce truc
Je suis à peu près sûr que cela est indéfini (ou de la mise en œuvre définie, ou d'autres "Ne fais pas cela si vous voulez que le code fonctionne toujours sur une plate-forme"), donc probablement ne fonctionnera probablement pas nécessairement.
@Matspetersson Il est défini et fonctionnera sur tous les JVM, qu'il soit 32 bits ou 64 bits. Java a tendance à définir tous les cas de bord, contrairement à certaines des langues plus anciennes. ;)
Désolé, mon point était que "cela ne fonctionne que dans certaines circonstances dans d'autres langues que Java".
@MATSPETERSSON C'est un comportement indéfini dans C.
Je pense que JLS3 15.19 peut être interprété de cette façon. "C'est comme si l'opérande de droite a été soumis à un boeuf logique et opérateur et avec la valeur de masque 0x1f." Cela fait de cela la réponse correcte (seulement?).
Au fait, Java fait cette opération [pour des valeurs normales] plus lentes [à moins que le compilateur ne puisse trier le coup] en définissant des "cas de bord" tels que ceci, où C / C ++ le rend indéfini [qui ne signifie pas ", il ne veut pas Faites ce que vous attendez », mais cela ne peut pas faire ce que vous attendez - en particulier, il finira par changer de 61 bits sur un nombre de 32 bits sur un PowerPC [je pense que c'était un exemple utilisé précédemment pour une question similaire], mais "travailler va" sur x86].
@MatSpetersson Si cela est vrai, c'est un bug dans le JVM qui devrait être fixé à un moment donné. Vous ne pouvez pas vous protéger de bugs dans des opérations de base complètement.
Désolé, je pense que vous avez mal compris. Je m'attends à ce que le jvm le fait "correctement" dans le sens où il est défini. Mais la solution C / C ++ n'est indéfinie de sorte que vous n'avez pas besoin d'avoir un "Y << (x & bits_in (y) -1)`, ajouter une opération supplémentaire et opération sur tous les quarts de travail qui n'a pas de constante [ Évidemment, pour une constante, le compilateur peut le trier quand même].
x << (32-3) == 0 pour un int ; x << (64-3) == 0L pour un long .
Les deux expressions déclenchent un comportement indéfini dans C.
@ouah je crois que la plupart des programmes C font une utilisation intensive de comportement non défini.
Le moyen le plus simple de vérifier la divisibilité de N par 9 est de faire n% 9. Une autre méthode consiste à résumer les chiffres de n. Si la somme des chiffres est multiple de 9, alors n est multiple de 9. Les méthodes ci-dessus ne sont pas des méthodes basées sur les opérateurs bitwises et nécessitent une utilisation de '%' et '/'. Les opérateurs bitwises sont généralement plus rapides que les opérateurs de modulo et de division. Voici une méthode basée sur l'opérateur bitwise pour vérifier la divisibilité par 9.
Vous devriez vérifier ce lien http://www.firmcodes.com/check-number- Multiple-9-Utilisation-Opérateurs-Opérateurs /
pour l'amour de la simplicité strong> Si vous souhaitez savoir si un entier N est un multiple de x, étant X une puissance de 2, juste faire: p> N & (X-1) with N = 9, X=8
N(9) = 1001
X(8-1) = 0111
N&(X-1) = 0001 this case is != 0
N(16) = 10000
X(8-1) = 00111
N&(X-1) = 00000 this time is == 0, it is a multiple.
if (((x >> 3) << 3) == x)
divisibleBy8 = true;
This would fail for the input 0 (zero)
Astuce, le changement de droite est la même chose que la division par 2
@Stevekuo en C, uniquement pour les entiers positifs
et 8 est 2 * 2 * 2;)
@ouah il y a des changements de droite préservant des panneaux. Je crois que la syntaxe C est
num >>> 3 .@ Sergeyl. - C'est la syntaxe Java. Dans C et C ++, il n'y a pas de signe de préservation de la signalisation d'une valeur négative; Un changement de droite d'un nombre négatif a un comportement défini par la mise en œuvre.
@Petebecker Cheers, je savais que je l'ai vu quelque part. Je sais qu'il y a une instruction X86 qui préservant les panneaux de signes.
sonne comme une question d'entretien Amazon
retour! (x & (8-1));