Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

JavaScript Discussion :

Manipulation binaire 64 bits


Sujet :

JavaScript

  1. #1
    Nouveau membre du Club
    Manipulation binaire 64 bits
    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 ?

  2. #2
    Expert confirmé
    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 à 252 -1 pour tous les valeurs manipulées en précision sur javascript ( norme IEEE_754 )
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

  3. #3
    Rédacteur



    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

  4. #4
    Nouveau membre du Club
    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

  5. #5
    Expert confirmé
    Citation Envoyé par TomHardcore_ Voir le message
    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)
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

  6. #6
    Nouveau membre du Club
    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

  7. #7
    Expert confirmé
    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.
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

  8. #8
    Expert confirmé
    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
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

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

  10. #10
    Expert éminent
    Ce message n'a pas pu être affiché car il comporte des erreurs.
    Cette signature n'a pas pu être affichée car elle comporte des erreurs.

  11. #11
    Expert confirmé
    Citation Envoyé par Watilin Voir le message
    Bonsoir&#8239;!
    Je vois que plusieurs personnes ont mentionné la norme IEEE-754, mais en réalité le problème n’est pas là&#8239;: 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&#8239;— 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.
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

  12. #12
    Expert éminent
    Je partage ce lien parce qu’il m’a appris quelques trucs&#8239;: https://developer.mozilla.org/fr/doc...teurs_binaires
    Notamment, on peut «&#8239;décaler sans bouger&#8239;» 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 «&#8239;gratter&#8239;» le 32e 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&#8239;: https://github.com/Watilin/binops
    Cette signature n'a pas pu être affichée car elle comporte des erreurs.

  13. #13
    Expert confirmé
    Citation Envoyé par Watilin Voir le message

    Notamment, on peut «&#8239;décaler sans bouger&#8239;» 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 «&#8239;gratter&#8239;» le 32e 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
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode

  14. #14
    Nouveau membre du Club
    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 :')

  15. #15
    Expert éminent sénior
    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.
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  16. #16
    Expert confirmé
    Citation Envoyé par Neckara Voir le message
    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
    «La pluralité des voix n'est pas une preuve, pour les vérités malaisées à découvrir, tant il est bien plus vraisemblable qu'un homme seul les ait rencontrées que tout un peuple.» [ René Descartes ] - Discours de la méthode