表示一个数字所需的位数

Question

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

方法1:

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

方法2：

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之间的数字呢？

谢谢。

- Jason Gooner

---

请参见https://dev59.com/KnRB5IYBdhLWcg3wQFPu。 - hippietrail

Answer 1

你可以这样做：

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

Number 的 toString() 方法可以接受一个进制作为可选参数。

这里有一些测试。在 Chrome、Safari、Opera 和 Firefox 上能正常工作，但抱歉无法在 IE 上使用。

- Anurag

Answer 2

位运算在JavaScript中仅对32位以下的“整数”可靠地工作。引用自完整的JavaScript数字参考资料：

在JavaScript中，位运算有点像黑客技巧。由于JavaScript中的所有数字都是浮点数，并且位运算符仅适用于整数，因此JavaScript会在幕后进行一些魔法操作，以使它看起来像是将位运算应用于32位带符号整数。

具体来说，JavaScript取你正在工作的数字并取该数字的整数部分。然后，将整数转换为该数字所表示的最多比特数，最多31位（1位为符号位）。因此0将创建一个两位数（符号为1，0位），同样1将创建两位。2将创建三位数，4将创建四位数，依此类推......

重要的是要意识到您不能保证获得32位数字，例如理论上not对零进行运行应将0转换为4,294,967,295，但实际上它将返回-1，原因有两个：第一，JavaScript中所有数字都带有符号，因此“not”始终反转符号；第二，JavaScript无法从数字0中生成多个位，而非零变为1。因此~0=-1。

因此，在JavaScript中的位运算符最多使用32位。

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

- fmark

---

第三段有点傻。我不知道数字在 ~0运算中实际是如何存储的，但即使它以32位存储，-1仍然是完全合理的。0 == 0x00000000 和 ~0 == 0xFFFFFFFF（所有位都设置为1）。作为带符号的32位整数，0xFFFFFFFF == -1使用二进制补码。 - robyoder

Answer 3

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

- trincot

Answer 4

虽然有些晚了，但我想夸赞trincot的32位答案，并提供一个更快、更简单、更好支持完整53位方法。

以下两个示例只是读取/解析并返回浮点数的指数值。

对于支持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和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，代表传递的整数Number所需的最大位数。它们在整个范围[-2⁵³, 2⁵³]内无误，并且超出此范围，覆盖了正浮点指数的全部范围，除非输入Number已经发生舍入（例如2⁵⁵-1）被存储为2⁵⁵（显然等于56位）。

解释IEEE 754浮点格式真的超出了本答案的范围，但对于那些有基本理解的人，我在下面包含了一个折叠的片段，其中包含一个表格形式的计算，可以从中看到/解释逻辑：实际上我们只是获取浮点数的第一个字（16个MSB包含符号和完整指数），减去4位移位偏移量和零偏移量（节省了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）允许实现者自由选择如何实现语言。因此，在跨浏览器的世界中，不仅需要处理舍入差异，还需要处理不同的算法，例如Math.log和Math.log2等。
正如您已经注意到的那样（您的方法1），log2（polyfill）可能无法使用的常见示例是2⁴⁸（=49，当向下取整时为1），但这不是唯一的例子。
例如，某些版本的Chrome甚至会出现明显更小的数字错误，如：Math.log2(8) = 2.9999999999999996（向下取整时少了一个）。
在这个stackoverflow Q / A中了解更多信息：Math.log2 precision has changed in Chrome。
这意味着我们无法知道何时将我们的对数结果向下取整或向上取整（或在舍入之前轻松预测我们是否已经偏离一个）。

所以你可以在循环中计算输入数字被2整除的次数，直到小于1（类似于你计算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的answer中所述，本质上是：return n && n.toString(2).length;（假设浏览器可以给出至少53位的结果）。

- GitaarLAB

Answer 5

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

- Joey