9
votes

Nombre de bits pour représenter un nombre

J'essaie d'écrire une fonction pour renvoyer le nombre de bits un entier positif moins que la limite JavaScript de (2 ^ 53) -1 est. Cependant, je suis frappé par des problèmes de précision et je veux éviter les bibliothèques de grandes entières.

Méthode 1: P>

function bitSize(num)
{
var count = 0;
while(num > 0)
{
    num = num >> 1;
    count++;
}
return count;
}

Pass: bitSize( Math.pow(2, 16) -1 ) = 16
Pass: bitSize( Math.pow(2, 16) ) = 17
Fail (Should be 48): bitSize( Math.pow(2, 48) -1 ) = 1
Fail (Should be 49): bitSize( Math.pow(2, 48) ) = 1


5 Réponses :


1
votes

Construisez une table de recherche avec les limites respectives où les bits changent. Vous ne pouvez le faire pour que les valeurs plus grandes ne soient plus grandes et encore plus petites dans le logarithme. Il semble que ce soit généralement dans le point flottant, car je peux aussi la reproduire dans PowerShell ici.


0 commentaires

10
votes

Vous pouvez faire: xxx

le tostring () méthode de numéro prend le radix comme argument facultatif.

Voici quelques tests . Fonctionne sur Chrome, Safari, Opera et Firefox. Pas d'accès à IE, désolé.


0 commentaires

10
votes

les opérations ne fiable au niveau du bit travailler Javascript pour "entiers" jusqu'à 32 bits. Pour citer Le code JavaScript complet Numéro de référence :

opérations sont un peu au niveau du bit d'un hack en Javascript. Étant donné que tous les numéros Javascript sont à virgule flottante, et les opérateurs ne fonctionnent sur bitwise entiers, Javascript fait un peu derrière la magie des scènes pour le faire apparaissent des opérations au niveau du bit sont en cours appliquée à un entier signé 32 bits.

Plus précisément, Javascript prend la numéro que vous travaillez et prend la partie entière du nombre. Ce puis convertit le nombre entier le plus nombre de bits que ce nombre représente, jusqu'à 31 bits (1 bit pour le signe). Donc 0 créer un certain nombre de deux bits (1 pour le signe et 1 bit de 0), également 1 créerait deux bits. 2 créerait un numéro 3 bits, 4 créerait un 4 bits nombre, etc ...

Il est important de réaliser que vous êtes non garanti un numéro de 32 bits, pour par exemple en cours d'exécution sur le zéro ne doit, en théorie, convertir 0 à 4294967295, Au contraire, il retournera -1 pour deux raisons, la première étant que tous les numéros sont signés en Javascript afin « Non » provoque toujours l'inversion du signe, et deuxième Javascript ne pouvait pas faire plus d'un bit à partir du nombre zéro et zéro devient. Par conséquent ~ 0 = -1.

signes en Javascript sont au niveau du bit up à 32 bits.

Comme les notes Anurag, vous devez simplement utiliser le intégré num.toString (2) dans cette situation au lieu, qui délivre une chaîne de longueur minimale de l'ASCII '1' et '0' s, vous pouvez simplement prendre la longueur.


1 commentaires

Ce troisième paragraphe est un peu stupide. Je ne sais pas comment les chiffres sont réellement stockés dans une opération ~ 0 , mais -1 permet toujours de comprendre le sens même s'il est stocké dans 32 bits. 0 == 0x00000000 et ~ 0 == 0xFFFFFFFFF (tous les bits définis sur 1). En tant qu'integer 32 bits signé, 0xffffffff == -1 en utilisant le complément de deux.



4
votes

La norme ES6 apporte math.clz32 () code> , donc pour les chiffres dans la plage de 32 bits, vous pouvez écrire: xxx pré>

Testez-le dans cet extrait: p>

p>

Math.imul = Math.imul || function(a, b) {
  var ah = (a >>> 16) & 0xffff;
  var al = a & 0xffff;
  var bh = (b >>> 16) & 0xffff;
  var bl = b & 0xffff;
  // the shift by 0 fixes the sign on the high part
  // the final |0 converts the unsigned value into a signed value
  return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
};

Math.clz32 = Math.clz32 || (function () {
  'use strict';

  var table = [
    32, 31,  0, 16,  0, 30,  3,  0, 15,  0,  0,  0, 29, 10,  2,  0,
     0,  0, 12, 14, 21,  0, 19,  0,  0, 28,  0, 25,  0,  9,  1,  0,
    17,  0,  4,   ,  0,  0, 11,  0, 13, 22, 20,  0, 26,  0,  0, 18,
     5,  0,  0, 23,  0, 27,  0,  6,  0, 24,  7,  0,  8,  0,  0,  0]

  // Adapted from an algorithm in Hacker's Delight, page 103.
  return function (x) {
    // Note that the variables may not necessarily be the same.

    // 1. Let n = ToUint32(x).
    var v = Number(x) >>> 0

    // 2. Let p be the number of leading zero bits in the 32-bit binary representation of n.
    v |= v >>> 1
    v |= v >>> 2
    v |= v >>> 4
    v |= v >>> 8
    v |= v >>> 16
    v = table[Math.imul(v, 0x06EB14F9) >>> 26]

    // Return p.
    return v
  }
})();

document.body.textContent = 32 - Math.clz32(0b1000000);


0 commentaires

1
votes

tard à la fête, mais je veux complimenter 32 bits de Trincot Répondre avec un plus rapide, plus simple et mieux supporté Méthode complète 53 bits.

Les 2 exemples suivants vont simplement lire / analyser et renvoyer la valeur de l'exponent du flotteur. P>

pour les navigateurs modernes qui supportent ES6 arraybuffer code> et DataView code> (ne se soucie pas de la plate-forme Endansness mais avec moins de compatibilité de l'héritage): p> xxx pré>

P>

Exemple pour les navigateurs légèrement plus anciens qui supportent float64Array code> et uint16array morue e> (mais non dataview code>, alors endiangité est dépendante de la plate-forme et cet extrait suppose "standard" petit-endian): p> xxx pré>

P>

Les deux versions ci-dessus renvoient un entier positif numéro code> représentant les bits maximum em> nécessaires pour maintenir le numéro d'un intégrité code> qui a été passé comme argument.
Ils travaillent sans erreur sur toute la plage de [-2 53 sup>, 2 53 sup>] strong>, et au-delà, couvrant la gamme complète de flotteurs Les exposants de points flottants sauf em> où l'arrondi déjà survenu sur l'entrée numéro code> (par exemple 2 55 sup> -1) em> stocké Comme 2 55 sup> (qui, évidemment, fait em> 56 bits égaux). p>

Expliquer le format Point flottant IEEE 754 est vraiment en dehors de la portée de cette réponse , mais pour ceux qui comprennent une compréhension de base, j'ai inclus l'extrait effondré ci-dessous qui contient un calcul de la forme de table à partir duquel on peut voir / expliquer la logique: nous sommes effectivement saisis le premier mot du flotteur (16 MSB contenant le panneau et l'exposant complet. ), Soustrayez le décalage décalé à 4 bits et la zeroing_offset (des opérations US 2), le résultat du décalage et du masque en tant que sortie. 0 code> est pris en charge dans la fonction. p>

p>

function reqBits4Int(n){ 'use strict';
  var r= 4294967295 < n  ? ( n= n/4294967296 >>>   0,      32 ) : 0 ;
              65535 < n && (               n >>>= 16,  r+= 16 );
                255 < n && (               n  >>=  8,  r+=  8 );
                 15 < n && (               n  >>=  4,  r+=  4 );
  //              3 < n && (               n  >>=  2,  r+=  2 ); 
  //              1 < n && (               n  >>=  1,  r+=  1 ); 
  // return r + n;

  // OR using a lookup number instead of the lines comented out above
  // position: 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0  = 16 values
  //   binary: 11 11 11 11 11 11 11 11 10 10 10 10 01 01 00 00  = 4294945360 dec

  return (n && (4294945360 >>> n * 2 & 3) + 1) + r;
}


0 commentaires