Manipulation binaire 64 bits

**TomHardcore_** · 03/04/2018, 19h02

Bonjour,

Pour mon projet (dont je doit rendre un premier contre-rendu le 20 avril :'( ) J'ai un gros problème que je n'arrive pas à résoudre depuis plusieurs semaine. Je dispose d'une grille de 64 cases. Pour modéliser un ensemble de position d'un type objet B donné, je voulais coder des entiers sur 64 bits où si B est présent à la i-ème case, alors le i-ème bit vaudra 1 et sinon 0. Comme ça si je veux savoir si des ensembles on des positions en commun ou aucune, inclusion d'ensemble etc.. j'étais sensé pourvoir utilisé les opérations logique & || (intersection, inclusion) pour pouvoir gagner du temps. Malheureusement, quand je teste avec des petits nombres, pas de problème mais avec de grand nombre ça me renvoie soit un truc qui n'a rien à voir, soit 0.

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
console.log((111 & 101)); // renvoie 101 comme attendue
 
console.log((1001000000 & 1000000000)); // renvoie 998901760
 
console.log((998901760).toString(2)); // Mais en binaire ça correspond à 111011100010100000100000000000

Est-ce un problème d'encodage avec les grands nombres ou il y a un moyen de contourner ça ?

**psychadelic** · 03/04/2018, 20h15

la valeur 1001000000 vaut 111011101010100000110001000000 en binaire
la valeur 1000000000 vaut 111011100110101100101000000000 en binaire

et un AND sur ces 2 valeurs donne bien un 111011100010100000100000000000 binaire soit 998901760 en système décimal.

donc, ou est le problème ???

sinon depuis ECMAScript 6 tu peux écrire tes variables en binaire en les précédent d'un 0b (chiffre zéro suivit d'un b)

exemple
var monBinaire = 0b101; // = valeur 5 en décimal.

reste bien sur la limtation à 2⁵² -1 pour tous les valeurs manipulées en précision sur javascript ( norme IEEE_754 )

**danielhagnoul** · 03/04/2018, 20h37

JavaScript utilise la norme IEEE-754, soit une précision sur quinze à seize chiffres décimaux.

Pour les grands nombres, il existe des bibliothèques externes, par exemple : BigNumber et Int64.

node-int64 : https://stackoverflow.com/questions/...4-bit-integers
Big Number : http://jsfromhell.com/classes/bignumber

**TomHardcore_** · 03/04/2018, 21h25

Donc imaginons que j'ai un entier N = 1152923153874288600. Je veux afficher le résultat de N AND N.

Si je fais console.log(1152923153874288600 & 1152923153874288600 ); // affiche 0 au lieu de N
ça m'affiche 0 car l'entier est trop grand par rapport à la précision ?

vu qu'en binaire c'est censé être le même chiffre

**psychadelic** · 03/04/2018, 22h15

Envoyé par TomHardcore_

vu qu'en binaire c'est censé être le même chiffre

dans l'absolu, oui, c'est le même chiffre.

Mais la, tu utilise le langage Javascript et qui utilise la norme IEEE-754 pour fixer la limite de la grandeur maxi des chiffres qu'il peut traiter.

Et comme l' écrit danielhagnoul si tu veux utiliser une plus grande précision il faut utiliser BigNumber ou Int64 ou encore une bibliothèque de calcul comme Numeral.js ou decimal.js.

mais même ces bibliothèques ont leurs limitations et on ne peut pas les utiliser pour faire des calculs astronomiques.

Le principe de la représentation binaire utilisé par JavaScript est de tenir dans un registre du microprocesseur et celle-ci est actuellement fixée à 64 bits, c'est à dire en utilisant une mantisse des 52 digits binaires, une partie exposant de 11 bits, et le dernier 1 bit est utilisé pour indiquer le signe.
Le jeu d’instruction en assembleur des processeurs 64bits sont câblés pour faire l'ensemble des opérations arithmétiques, booléennes, trigonométriques, etc.. , sur 64bits.

Les interpréteurs JavaScript sont écrits pour ce type de processeurs sur 64bits.

Ton chiffre à 19 digits ne rentre pas dans une écriture binaire sur 52 digits, et il en résulte qu'il ne peut pas être pris en compte pour des les opérations booléennes et renvoie donc zéro.

test =>

Code JavaScript :

Sélectionner tout - Visualiser dans une fenêtre à part

alert (Number.isSafeInteger(1152923153874288600)); // renvoie false)

**TomHardcore_** · 03/04/2018, 22h30

Hmm Je comprends. Le nombre le plus grand que je suis succeptible d'avoir besoin est 2^64 donc c'est carrément mort. Je pense que je vais tout simplement me tourner vers une autre solution pour gérer mes ensembles... merci quand même

**psychadelic** · 03/04/2018, 23h00

Si tu n'a juste que le soucis de faire les 4 ou 5 opérations booléennes sur tes valeurs, alors tu peux facilement t'écrire ta propre librairie dans un objet JavaScript qui manipulerai des strings remplis de zéro et de un.

**psychadelic** · 04/04/2018, 00h08

Kdo :

Code JavaScript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
var BooleStr = {
  _Bs1:'',
  _Bs2:'',
  _Rep:'',
  _isBINARY: function(S) {
    return (/^[0-1]*$/).test(S);
  },
  _prep:function(s1,s2 ) {
    let l1 = s1.length, l2 = s2.length, lx = l1 - l2;
    this._Rep='';
 
    if (this._isBINARY(s1) && this._isBINARY(s2)) {
      this._Bs1 = (lx < 0) ? '0'.repeat(-lx) + s1 : s1;
      this._Bs2 = (lx > 0) ? '0'.repeat(lx) + s2 : s2;
      return Math.max(l1, l2);
    } else {
      this._Rep='error: non binaire';
      return 0;
    }
  },
  _getVal:function(S,p){
    let l=S.length-1;
    if(p>l) return NaN;
    if(this._isBINARY(S)) return ( S[l-p]==='1' );
    else return 'error: non binaire';
  },
  _setVal:function(S,p,v){
    let l=S.length-1;
    this._Rep = (p>l)?'0'.repeat(p-l)+S:S;
    l=Math.max(l,p) -p;
    this._Rep = this._Rep.substr(0,l)+((v)?'1':'0')+this._Rep.substr(l+1);
    return this._Rep;
  },
  _NOT: function(S) {
    let l = S.length;
    this._Rep='';
 
    if (this._isBINARY(S)) {
      for (let i=0; i<l; i++) {
        this._Rep += (S[i]==='0')?'1':'0';
      }      
    }
    return this._Rep;
  },
  _AND:function(S1, S2) {
    let l=this._prep(S1, S2);
    for (let i=0; i<l; i++) {
     this._Rep += (this._Bs1[i] === this._Bs2[i]) ? this._Bs1[i] : '0';
    }
    return this._Rep;
  },
  _OR: function(S1, S2) {
    let l=this._prep(S1, S2);
    for (let i=0; i<l; i++) {
     this._Rep += (this._Bs1[i] === '1' || this._Bs2[i] === '1') ? '1' : '0';
    }
    return this._Rep;
  },
  _NOR: function(S1, S2) {
    let l=this._prep(S1, S2);
    for (let i=0; i<l; i++) {
     this._Rep += (this._Bs1[i] === '0' && this._Bs2[i] === '0') ? '1' : '0';
    }
    return this._Rep;
  },
  _XOR: function(S1, S2) {
    let l=this._prep(S1, S2);
    for (let i=0; i<l; i++) {
     this._Rep += (this._Bs1[i]==='1' || this._Bs2[i]==='1')?((this._Bs1[i] != this._Bs2[i]?'1':'0')):'0';
    }
    return this._Rep;
  }
};
 
console.log('1010 AND 1101 => ' + BooleStr._AND ('1010', '1101') );  // 1000
console.log('1a10 OR  1101 => ' + BooleStr._OR  ('1a10', '1101') );  // error: non binaire
console.log('1010 OR  1101 => ' + BooleStr._OR  ('1010', '1101') );  // 1111
console.log('1010 XOR 1101 => ' + BooleStr._XOR ('1010', '1101') );  // 0111  
console.log('   1 OR  1101 => ' + BooleStr._OR  (   '1', '1101') );  // 1101
console.log('   1 NOR 1101 => ' + BooleStr._NOR (   '1', '1101') );  // 0010
console.log('1000 XOR    1 => ' + BooleStr._XOR ('1000',    '1') );  // 1001 
 
console.log('binaire ? =fg01e= ' + BooleStr._isBINARY ('f01ghe' ));  // false
console.log('binaire ? =01001= ' + BooleStr._isBINARY ('01001' ));   // true
 
console.log('val binaire pos=0  00001 ' + BooleStr._getVal ('00001',0 )); // true
console.log('val binaire pos=2  00100 ' + BooleStr._getVal ('00100',2 )); // true
console.log('val binaire pos=4  00100 ' + BooleStr._getVal ('00100',4 )); // false
console.log('val binaire pos=8  00100 ' + BooleStr._getVal ('00100',8 )); // NaN
 
console.log('setVal("00100",1,true) -> '+  BooleStr._setVal ('00100', 1, true )); // 00110
console.log('setVal("00100",12,true) -> '+  BooleStr._setVal ('00100', 12, true )); // 1000000000100
 
console.log(' _NOT =01001= ' + BooleStr._NOT ('01001' ));   // 10110

plutôt fun à coder

**Beginner.** · 04/04/2018, 21h24

Ah un fil intéressant, j'en aurais peut-être besoin plus tard...

**Watilin** · 04/04/2018, 21h39

Bonsoir !
Je vois que plusieurs personnes ont mentionné la norme IEEE-754, mais en réalité le problème n’est pas là : il se situe au niveau des opérations binaires elles-mêmes.
Pour des raisons que j’ignore, JavaScript est capable de manipuler des nombres entiers exacts dans la limite de [ -2⁵³ + 1 ; 2⁵³ - 1 ], sauf quand on fait des opérations binaires dessus — ils sont alors limités à 32 bits.

Ça donne lieu à des aberrations du genre : (2 ** 31) | 0 qui déborde et renvoie un nombre négatif.

Ainsi, ce n’est pas la représentation qui est en cause, mais bel et bien les opérateurs qui sont défectueux. Pour contourner le problème, il faut décider d’une représentation maison des binaires sur plus de 32 bits, et à la place des opérateurs natifs, utiliser des fonctions qu’on aura écrites soi-même. Exactement ce que propose psychadelic

**psychadelic** · 04/04/2018, 22h38

Envoyé par Watilin

Bonsoir !
Je vois que plusieurs personnes ont mentionné la norme IEEE-754, mais en réalité le problème n’est pas là : il se situe au niveau des opérations binaires elles-mêmes.
Pour des raisons que j’ignore, /.../ quand on fait des opérations binaires dessus — ils sont alors limités à 32 bits.

Oui, c'est curieux!
ça fait des siècles que je n'ai pas codé en assembleur ,mais cela me laisse croire que les instructions Booléenes sont uniquement câblées pour fonctionner sur des registres de 32bits... ???

PS si vous avez d'autres idées d'instructions "Booléennes" à implémenter, je pense ouvrir ici un sujet à part sur cette question, gardez vos notes.
J'ai moi-même d'autres idées, faut juste que je prenne le temps de les mettre en forme.

**Watilin** · 05/04/2018, 03h11

Je partage ce lien parce qu’il m’a appris quelques trucs : https://developer.mozilla.org/fr/doc...teurs_binaires
Notamment, on peut « décaler sans bouger » un nombre si on décale de zéro bits. Le décalage avec insertions de zéros, >>>, va changer le bit de signe à zéro, et le nombre va passer en non signé.

Ça permet de « gratter » le 32^e bit. Malheureusement ça ne permet pas d’aller au-delà.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
console.log(-9 | 0); // -9
console.log(-9 >>> 0); // 4294967287
console.log((-9 >>> 0) > 2**31); // true

Ça permet aussi d’avoir des représentations en bases 2 et 16 un peu plus utiles…

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
console.log((-9).toString(2)); // "-1001"
console.log((-9).toString(16)); // "-9"
 
console.log((-9 >>> 0).toString(2)); // "11111111111111111111111111110111"
console.log((-9 >>> 0).toString(16)); // "fffffff7"
 
console.log(0xfffffff7); // 4294967287
console.log(0xfffffff7 | 0); // -9

En attendant, j’ai commencé à bricoler un truc : https://github.com/Watilin/binops

**psychadelic** · 05/04/2018, 14h53

Envoyé par Watilin

Notamment, on peut « décaler sans bouger » un nombre si on décale de zéro bits. Le décalage avec insertions de zéros, >>>, va changer le bit de signe à zéro, et le nombre va passer en non signé.

Ça permet de « gratter » le 32^e bit. Malheureusement ça ne permet pas d’aller au-delà.

En assembleur, cette instruction s'appelle "shift Left / right" (SLL / SRL voir => https://en.wikipedia.org/wiki/IBM_Ba...and_successors)
et suivant les microprocesseurs il existe d'autres types de décalage:
SLL / SRL <=> Shift Left Logical, Shift Right Logical,,
mais aussi SLR ou SRR , R comme Rotate, le bit "perdu" revenant par la droite ou par la gauche.
ou encore SLA ou SRA , A comme Arithmétique, qui injecte un zéro par la droite ou par la gauche, car ce décalage revient en fait à une multiplication ou une division par 2.

Je ne me souviens plus comment,mais le bit perdu se retrouvait dans un registre qui permettait d'en tester directement la valeur, pour savoir si le chiffre est pair ou impair, positif ou négatif; et après on remettait un décalage inverse, histoire de laisser le chiffre intact, l'instruction SSL ou SSR récupérant le bit en l'état.
sauf à faire un SSL puis un SRA, histoire de calculer la valeur absolue avec seulement 2 instructions, ce qui est moins couteux que d'en passer par un masque logique.

Dans l'exemple de ta page, https://developer.mozilla.org/fr/doc...teurs_binaires avec les 4 flags (araignée, belette, chat, dinosaure)
on utiliserai cette instruction de shift à droite pour récupérer un par un l'état de chaque flag, ce qui est beau coup simple à coder.

plutôt que des flags avec des noms de bestioles on peut aussi utiliser ce système pour vérifier la qualité d'un mot de passe, avec pour noms de flags pour vérifier si :
- il y a une lettre Majuscule
- il y a une lettre minuscule
- il y a un chiffre
- il y a plus de 8 caractères
- ...
et si tous les flags sont à un alors le mot de passe est jugé comme acceptable...

sinon, l'utilisation des décalages est intensivement utilisé dans l’algorithme d' Udi Manber et Sun Wu : agrep (Aproximative Grep) qui figure parmi les tout logiciels fournis en open source.
le décalage y est ici utilisé pour injecter la position des caractères identique avec la chaine de référence, car la lecture 1 caractère à la fois, le test se faisant quand le nombre de caractères est suffisant pour être évalué avec la longueur de la chaine de référence, le plus d'agrep étant de laisser la possibilité gérer une tolérance sur la suite suite de lettres https://www.tgries.de/agrep/agrephlp.html

**TomHardcore_** · 08/04/2018, 17h44

Je ne vais pas pouvoir créer et utiliser correctement ma propre lib de manipulation binaire en si peu de temps, je n'ai pas le niveau du coup je suis passé par une toute autre manière pour mon projet de fin d'année. Mais pendant les vacances, je reviendrais sûrement sur ce topic pour retravailler mon idée de départ. En tout cas ce problème m'a appris bien des choses sur le javascript :')

**Neckara** · 28/06/2019, 07h20

Bibliothèque intéressante, à quand un paquet npm ?

Le problème d'utiliser des strings est que cela rend les opérations très peu performantes, que ce soit en consommation mémoire ou en temps d'exécution. Or les opérations bits à bits sont très utilisés, donc la moindre pertes en temps d'exécution peut être importante.

Je pense qu'il serait plus performant d'utiliser ton propre type qui représenterait en interne un Uint32Array et que tu pourrais construire à partir de n'importe quoi. Tu pourras ensuite faire les opérations binaires de manières très efficace, considérant qu'il n'y au maximum que 31 bits par éléments de ton array.

Il faut aussi éviter les opérateurs ternaires, ils sont bien plus coûteux qu'un if/else. Il faut aussi éviter au maximum tout ce qui est conditionnel si on veut maximiser les performances.

**psychadelic** · 28/06/2019, 13h13

Envoyé par Neckara

Bibliothèque intéressante, à quand un paquet npm ?

merci

, ça fait plaisir.
Mais comme tu l'a souligné toi-même, c'est une "bibliothèque" peu performante; je ne l'envisageais pas pour une utilisation intensive, le défi était juste de s'affranchir du mur des 32bits

Manipulation binaire 64 bits

JavaScript

Discussions similaires

Partager

Partager