javascript - 表示数字的位数

Question

我正在尝试编写一个函数来返回小于 (2^53)-1 的 Javascript 限制的正整数的位数。但是我遇到了精度问题，并且希望避免使用大整数库。

方法一：

function bitSize(num)
{
return Math.floor( Math.log(num) / Math.log(2) ) + 1;
}

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 ) = 49 
Pass: bitSize( Math.pow(2, 48) ) = 49

方法二：

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

我认为这两种方法都无法解决精确问题。

谁能建议一种适用于 0 -> 2^53-1 之间数字的替代方法

谢谢。

score 11 · Accepted Answer

你可以做：

function bitSize(num) {
    return num.toString(2).length;
}

的toString()方法Number将基数作为可选参数。

这里有一些测试。适用于 Chrome、Safari、Opera 和 Firefox。无法访问 IE，抱歉。

score 10 · Accepted Answer

位运算只能在 Javascript 中可靠地用于高达 32 位的“整数”。 引用The Complete JavaScript Number Reference：

按位运算在 Javascript 中有点像 hack。由于 Javascript 中的所有数字都是浮点数，并且按位运算符仅适用于整数，因此 Javascript 在幕后做了一点魔术，以使其看起来按位运算应用于 32 位有符号整数。

具体来说，Javascript 采用您正在处理的数字并采用该数字的整数部分。然后它将整数转换为该数字表示的最多位数，最多 31 位（符号位为 1 位）。所以 0 将创建一个两位数（1 表示符号，1 位表示 0），同样 1 将创建两位数。2 将创建一个 3 位数字，4 将创建一个 4 位数字，等等……</p>
重要的是要意识到你不能保证一个 32 位数字，例如运行不为零，理论上应该将 0 转换为 4,294,967,295，而不是返回 -1，原因有两个，第一个是所有数字都用 Javascript 签名所以“不”总是反转符号，第二个Javascript不能从数字零中产生超过一位，而不是零变成一。因此~0=-1。

所以 Javascript 中的位符号最多为 32 位。

num.toString(2)正如 Anurag 指出的那样，您应该在这种情况下简单地使用内置函数，它会输出一个最小长度的 ASCII '1's 和'0's 字符串，您可以简单地取其长度。

score 4 · Accepted Answer

ES6 标准带来了Math.clz32()，因此对于 32 位范围内的数字，您可以编写：

num_bits = 32 - Math.clz32(0b1000000);

在这个片段中测试它：

var input = document.querySelector('input');
var bits = document.querySelector('#bits');

input.oninput = function() {
    var num = parseInt(input.value);
    bits.textContent = 32 - Math.clz32(num);
};

Number (Decimal): <input type="text"><br>
Number of bits: <span id="bits"></span>

在MDN 的 Math.clz32 文档中，提供了一个 polyfill：

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);

score 1 · Accepted Answer

建立一个查找表，其中包含位更改的相应边界。您可以仅对较大的值执行此操作，并且仍然通过对数执行较小的值。它似乎通常与浮点相关，因为我也可以在 PowerShell 中重现它。

score 1 · Accepted Answer

迟到了，但我想用一种更快、更简单和更好支持的完整 53 位方法来赞美 trincot 的 32 位答案。

以下 2 个示例将仅读取/解析并返回浮点数的指数值。

对于支持 ES6 的现代浏览器ArrayBuffer（DataView不关心平台的字节序，但遗留兼容性较差）：

reqBits4Int = (function(d){ 'use strict';
  return function(n){
    return n && (                         // return 0 if n===0 (instead of 1)
      d.setFloat64(0, n),                 // OR set float to buffer and
      d.getUint16(0) - 16352 >> 4 & 2047  // return float's parsed exponent
    );                                    // Offset 1022<<4=16352; 0b1111111=2047
  };                                      // DataView methods default to big-endian
})( new DataView(new ArrayBuffer(8)) );   // Pass a Buffer's DataView to IFFE

Float64Array支持and的稍旧浏览器的示例Uint16Array（但不支持DataView，因此字节序取决于平台，此代码段假定为“标准”小字节序）：

reqBits4Int = (function(){ 'use strict';
  var f = new Float64Array(1),            // one 8-byte element (64bits)
      w = new Uint16Array(f.buffer, 6);   // one 2-byte element (start at byte 6)
  return function(n){ 
    return ( f[0] = n                     // update float array buffer element
                                          // and return 0 if n===0 (instead of 1)
           ) && w[0] - 16352 >> 4 & 2047; // or return float's parsed exponent
  };  //NOTE : assumes little-endian platform
})(); //end IIFE

以上两个版本都返回一个正整数Number，表示保存作为参数传递的整数所需的最大位数。它们在 [-2 ⁵³ , 2 ⁵³ ]的整个范围内无错误地工作，除此之外，覆盖正浮点指数的整个浮点范围，除非输入已经发生舍入（例如 2 ⁵⁵ -1）被存储为 2 ⁵⁵（显然，它等于 56 位）。Number
Number

解释 IEEE 754 浮点格式确实超出了这个答案的范围，但对于那些有基本理解的人，我在下面包含了折叠的片段，其中包含表格形式的计算，从中可以看到/解释逻辑：实际上我们只需抓住浮点数的第一个字（16 个 MSB，包含符号和全指数），减去 4 位移位偏移和 zeroing_offset（节省我们 2 次操作），移位和掩码结果作为输出。0在功能中得到照顾。

<xmp> PREVIEW of data to be generated: 

Float value :  S_exponent__MMMM :  # -(1022<<4)#### :  #   >> 4     :    & 2047    : Result integer
         -9 :  1100000000100010 :  1000000001000010 :  100000000100 :          100 :     4
         -8 :  1100000000100000 :  1000000001000000 :  100000000100 :          100 :     4
         -7 :  1100000000011100 :  1000000000111100 :  100000000011 :           11 :     3
         -6 :  1100000000011000 :  1000000000111000 :  100000000011 :           11 :     3
         -5 :  1100000000010100 :  1000000000110100 :  100000000011 :           11 :     3
         -4 :  1100000000010000 :  1000000000110000 :  100000000011 :           11 :     3
         -3 :  1100000000001000 :  1000000000101000 :  100000000010 :           10 :     2
         -2 :  1100000000000000 :  1000000000100000 :  100000000010 :           10 :     2
         -1 :  1011111111110000 :  1000000000010000 :  100000000001 :            1 :     1
          0 :                 0 :   -11111111100000 :   -1111111110 :  10000000010 :  1026
          1 :    11111111110000 :             10000 :             1 :            1 :     1
          2 :   100000000000000 :            100000 :            10 :           10 :     2
          3 :   100000000001000 :            101000 :            10 :           10 :     2
          4 :   100000000010000 :            110000 :            11 :           11 :     3
          5 :   100000000010100 :            110100 :            11 :           11 :     3
          6 :   100000000011000 :            111000 :            11 :           11 :     3
          7 :   100000000011100 :            111100 :            11 :           11 :     3
          8 :   100000000100000 :           1000000 :           100 :          100 :     4
          9 :   100000000100010 :           1000010 :           100 :          100 :     4

after 18 the generated list will only show 3 values before and after the exponent change
</xmp>

<script> //requires dataview, if not available see post how to rewrite or just examine example above
firstFloatWord = (function(d){ 
  return function(n){
    return d.setFloat64(0, n), d.getUint16(0);
  };
})( new DataView(new ArrayBuffer(8)) );

function pad(v, p){
  return ('                    '+v).slice(-p);
}

for( var r= '',   i=-18, c=0, t
   ; i < 18014398509481984
   ; i= i>17 && c>=5
      ? (r+='\n', c=0, (i-2)*2-3)
      : (++c, i+1) 
   ){
  r+= pad(i, 19) + ' : '   
    + pad((t=firstFloatWord(i)).toString(2), 17) + ' : '
    + pad((t-=16352).toString(2), 17) + ' : '
    + pad((t>>=4).toString(2), 13) + ' : '
    + pad((t&=2047).toString(2), 12) + ' : '
    + pad(t, 5) + '\n';
}

document.body.innerHTML='<xmp>        Float value :  S_exponent__MMMM :  # -(1022<<4)#### : '
                       + ' #   >> 4     :    & 2047    : Result integer\n' + r + '</xmp>';
</script>

后备选项：

ECMAScript (javascript) 让实现者可以自由选择如何实现该语言。因此，在狂野的 x 浏览器世界中，不仅要处理舍入差异，还要处理不同的算法，例如Math.log等等Math.log2。
正如您已经注意到的（您的方法 1），一个log2(polyfill) 可能不起作用的常见示例是2 ⁴⁸（= 49，当地板时是一比一），但这不是唯一的例子。
例如，某些版本的 chrome 甚至会搞砸小得多的数字，例如：（Math.log2(8) = 2.9999999999999996落地时减少一到二）。
在此 stackoverflow Q/A 中阅读更多相关信息：Chrome 中的 Math.log2 精度已更改。
这意味着我们无法知道何时对数结果下限或上限（或在四舍五入 之前轻松预测我们何时已经过关）。

因此，您可以计算输入数字在循环中小于 1 之前除以 2 的频率（很像您计算的 32 位移位方法 2）：

function reqBits4Int(n){ for(var c=0; n>=1; ++c, n/=2); return c }

但这是相当蛮力的（也可能让你陷入四舍五入的问题）。您可以使用一些分而治之的方法来改进这一点，当您使用它时，展开循环：

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, 2 ⁵³ ]的正整数范围，没有错误（最多 2 ⁶⁴具有相同的可预测舍入-“错误”）。

或者，您可以尝试其他一些（重复，对于大于 32 位的输入值）的 bithacks。

最简单和最短的（但可能更慢，与上面的计算片段相比）是对数字进行字符串化并计算结果字符串长度，如 Anurag 的答案，本质上是：（return n && n.toString(2).length;假设浏览器可以给出高达（至少）53 的结果位）。

javascript - 表示数字的位数

5 回答 5

Related

Reference