Operateur rotation binaire [Résolu]

[xxkirastarothxx]

Bonjour à tous,

je suis entrain de retaper une application Javascript en python, et je suis tombé sur un problème:
à un moment dans le script, je tombe sur un ligne:

Code :

return (x<<n)

alors, je farfouille un peu et je trouve ceci sur un autre site :

<< :: Rotation à gauche :: Décale les bits vers la gauche (multiplie par 2 à chaque décalage). Les zéros qui sortent à gauche sont perdus, tandis que des zéros sont insérés à droite

Okay... alors, on refait le truc a la mano ensemble,
pour x = 1751007518
et n = 1

Code :

1
2
3
4
(dec)1751007518 = (bin)1101000010111100100000100011110
on décalle le bit : 11010000101111001000001000111100
(bin)11010000101111001000001000111100 = (dec)3502015036

Donc, okay, ça correspond bien à une multiplication par 2.
et c'est d'ailleur ce que python me reponds si je lui demande "1751007518<<1"

Alors.... pourquoi en javascript "alert(1751007518<<1)" me renvoie -792952260 ???? oO
en regardant d'un peu plus pres, Si on compare un peu les deux valeur binaire:

Code :

1
2
3
1101000010111100100000100011110  (1751007518)
__101111010000110111110111000100  (-792952260)

j'ai remarquer que les valeur en rouge était des inverses, mais c'est la seule piste que j'ai...
Ou peut être un problème avec le bit du signe ?

Donc voila, si quelqu'un à une explication, voir un bout de code (python) qui me permetrai de faire quelque chose l'équivalent ça serrait super ^^

[TheGwy]

Parce qu'en javascript il n'y a pas de nombres entiers.

Tout les nombres sont des Doubles IEEE 754 de 32 bits.

Donc quand tu fais un shift sur un grand nombre comme ça qui occupe déjà les 31 bits de ta mantisse et de ton exposant, tu débordes sur le 32ème bit qui sert au signe.

Enfin bon en gros : faire des opérations binaires en JS c'est la merde et c'est imprévisible.

http://fr.wikipedia.org/wiki/IEEE_75..._.2832_bits.29

Code :

1
2
3
4
5
6
7
8
9
10
11
12
var num = 1<<29;
//                                                     signe     exp               mantisse
//                                                          |       |                      |
//                                                         21098765432109876543210987654321
console.log(num, num.toString(2));         //   536870912    100000000000000000000000000000
console.log(num<<1, (num<<1).toString(2)); //  1073741824   1000000000000000000000000000000
console.log(num*2, (num*2).toString(2));   //  1073741824   1000000000000000000000000000000
 
num = 1<<30;
console.log(num, num.toString(2));         //  1073741824   1000000000000000000000000000000
console.log(num<<1, (num<<1).toString(2)); // -2147483648 -10000000000000000000000000000000
console.log(num*2, (num*2).toString(2));   //  2147483648  10000000000000000000000000000000

[TheGwy]

PS : de toute évidence c'est un bug dans ton programme d'origine, ne cherche pas à le reproduire.
Ou alors c'est réellement volontaire, mais alors c'est vraiment un gros hack bien sale et tu devrais réécrire quelque chose de plus stable que ce bricolage.

[Willpower]

Donc quand tu fais un shift sur un grand nombre comme ça qui occupe déjà les 31 bits de ta mantisse et de ton exposant, tu débordes sur le 32ème bit qui sert au signe.

+1

Enfin bon en gros : faire des opérations binaires en JS c'est la merde et c'est imprévisible.

Pour une fois, je ne suis pas d'accord avec toi, dieu du js, il faut juste savoir ce qu'on fait, comme pour tout code d'ailleurs.


Je travaille actuellement sur un code, qui compactes des données de tailles connues dans des nombres binaires avant des les convertir dans une autre bases pour les envoyer sous forme d'une chaine compactée.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// sauvegarde de 8 variables entières codées respectivement sur 6, 2, 1, 1, 2, 2, 4 et 6 bits sur les 32 bits d'une seule variable numérique
 
var varBin = 0;
varBin |= (donnee1_6bits & 63) << 18;
varBin |= (donnee2_2bits & 3) << 16;
varBin |= (donnee3_1bit & 1) << 15;
varBin |= (donnee4_1bit & 1) << 14;
varBin |= (donnee5_2bits & 3) << 12;
varBin |= (donnee6_2bits & 3) << 10;
varBin |= (donnee7_4bits & 15) << 6;
varBin |= (donnee8_6bits & 63);
 
// conversion de variable numérique en chaine de caractère base64 (6 bits) :
 
var _base64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
var code = '';
code += _base64.charAt((varBin >> 18) & 63);
code += _base64.charAt((varBin >> 12) & 63);
code += _base64.charAt((varBin >> 6) & 63);
code += _base64.charAt((varBin) & 63);

[TheGwy]

Oui tu as raison.
Ça ne sert à rien de se dire c'est de la merde sans essayer de comprendre.

D'ailleurs je pense que je me suis un peu planté plus haut quand je dis "Donc quand tu fais un shift sur un grand nombre comme ça qui occupe déjà les 31 bits de ta mantisse et de ton exposant, tu débordes sur le 32ème bit qui sert au signe."

Quand tu fais un shift, ton Double doit être convertit en int signé de 32 bits, et c'est dans cet int temporaire que tu déborde sur le 32ème bit de poids fort qui sert au signe.
Car faire un shift sur la représentation binaire d'un flottant cela n'a pas trop de sens.
Et cela explique aussi pourquoi une multiplication marche mais pas un shift : quand on multiplie, on ne convertit pas en int, et l'on reste dans dans une amplitude de valeurs exprimable avec un Double.

PS : de plus un Double c'est 64 et non 32 bits.

[xxkirastarothxx]

Merci pour ces explications, je pensais bien à quelque chose comme ça, sans véritablement savoir.

Mais alors, du coup, comment reproduire se "bug" dans un autre langage, car, effectivement, j'ai besoin de le reproduire, puisque les valeurs qui ont été calculées au préalable avec JS sont enregistrées, il faut donc que je puisse toujours faire la transition en python.

Peux être mieux faut il que je pause la question dans la partie python ?

encore merci

[TheGwy]

Envoyé par xxkirastarothxx

Merci pour ces explications, je pensais bien à quelque chose comme ça, sans véritablement savoir.

Mais alors, du coup, comment reproduire se "bug" dans un autre langage, car, effectivement, j'ai besoin de le reproduire, puisque les valeurs qui ont été calculées au préalable avec JS sont enregistrées, il faut donc que je puisse toujours faire la transition en python.

Peux être mieux faut il que je pause la question dans la partie python ?

encore merci

Bah du coup pour le reproduire c'est simple, il faut que tu utilise le même type de donnée intermédiaire : c'est à dire un integer signé de 32 bits.

Après la vrai question c'est de savoir si Python à ce type de donnée ou si tu dois faire appel à un package tiers qui l'implémenterais... pour ça effectivement, mieux vaut demander dans la section Python.

[xxkirastarothxx]

Et bien merci pour tout, je vais allé me renseigner de ce coté

[Willpower]

2 petites précisions en plus :

- es-tu certain que ton code atteint de valeurs extrêmes comme celle que tu as utilisais pour provoquer le bug ? parce que rotation binaire ou non, c'est étrange(inhabituel) d'utiliser d'aussi grandes valeurs.

- en fait :

Code :

1
2
1101000010111100100000100011110  (1751007518)
__101111010000110111110111000100  (-792952260)

792952260 = 2 * 1751007518 (mod 2^30)
(2^30 = plus grande puissance de 2 stockable sur 31 bits[0->30]... vu que le 32ème sert au signe)


1751007518 * 2 = 3502015036
2^30 = 1073741824

3502015036 mod 1073741824 = 280789564
280789564 - 1073741824 = -792952260


car si "101111010000110111110111000100" est bien la représentation binaire de 792952260 sa valeur négative n'est en réalité pas stockée sous cette forme en mémoire.

comme tu peux le voir ici, la représentation négative d'un nombre en machine se fait en complément à deux : http://fr.wikipedia.org/wiki/Syst%C3..._n.C3.A9gatifs

c'est pour cette raison que tu te retrouves avec tous les bits inversée (après troncage de ceux qui ont dépassé le 31 bit)