9

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 の間の数値で機能する代替方法を誰かが提案できますか

ありがとう。

4

5 に答える 5

11

できるよ：

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

のtoString()メソッドはNumber、オプションの引数として基数を取ります。

ここにいくつかのテストがあります。Chrome、Safari、Opera、および Firefox で動作します。IE にアクセスできません。申し訳ありません。

于 2010-06-20T23:25:59.500 に答える
10

ビット演算は、Javascript で 32 ビットまでの「整数」に対してのみ確実に機能します。The Complete JavaScript Number Reference から引用するには:

ビット単位の操作は、Javascript のちょっとしたハックです。Javascript のすべての数値は浮動小数点数であり、ビット単位の演算子は整数に対してのみ機能するため、JavaScript はバックグラウンドで少し魔法をかけて、ビット単位の操作が 32 ビットの符号付き整数に適用されているように見せます。

具体的には、Javascript は作業中の数値を取得し、その数値の整数部分を取得します。次に、整数を、number が表す最大ビット数 (最大 31 ビット (符号は 1 ビット)) に変換します。したがって、0 は 2 ビットの数値 (符号は 1、0 は 1 ビット) を作成し、同様に 1 は 2 ビットを作成します。2 は 3 ビットの数値を作成し、4 は 4 ビットの数値を作成します…</p>

32 ビットの数値が保証されていないことを認識することが重要です。たとえば、ゼロで実行されていない場合、理論的には 0 を 4,294,967,295 に変換する必要があります。代わりに、2 つの理由で -1 が返されます。最初の理由は、すべての数値が Javascript で署名されていることです。そのため、「not」は常に符号を反転し、2 番目の Javascript は数字のゼロから 1 ビットを超えて作成できず、ゼロではなく 1 になります。したがって、~0=-1 です。

したがって、Javascript のビット単位の符号は最大 32 ビットです。

Anurag が指摘しているように、この状況では代わりにビルトインを使用する必要があります。これは、単純に長さを取得できるASCII s とs のnum.toString(2)最小長の文字列を出力します。'1''0'

于 2010-06-20T23:29:54.890 に答える
4

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>

Math.clz32の MDN のドキュメントでは、ポリフィルが提供されています。

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

于 2016-04-20T13:42:48.013 に答える
1

パーティーに遅れましたが、trincot の 32 ビットの回答を、より速く、よりシンプルで、より適切にサポートされている完全な 53 ビットの方法で称賛したいと思います。

次の 2 つの例では、float の指数値を読み取り/解析して返します。

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


Float64Arrayandをサポートする少し古いブラウザの例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 53 , 2 53 ]の全範囲でエラーなく動作し、これを超えて、正の浮動小数点指数の全浮動小数点範囲をカバーします (入力で丸めが既に行われている場合(たとえば 2 55 -1)が格納されている場合を除く)。として 2 55 (明らかに、56ビットに等しい)。Number
Number

IEEE 754 浮動小数点形式の説明は、実際にはこの回答の範囲外ですが、基本的な理解がある人のために、論理を表示/説明できる表形式の計算を含む以下の折りたたまれたスニペットを含めました。 float の最初のワード (符号と完全な指数を含む 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) では、実装者が言語の実装方法を自由に選択できます。Math.logしたがって、野生の x ブラウザーの世界では、丸めの違いだけでなく、たとえばなどの異なるアルゴリズムにも対処する必要がありますMath.log2。
既にお気づきのように (方法 1)、log2(ポリフィル) が機能しない一般的な例は次のとおりです。 2 48 (= 1 対 49 で、床に置かれた場合) ですが、これが唯一の例ではありません。たとえば、Chrome の特定のバージョンでは、次のように非常に小さい数値を台無しにすること
さえありますMath.log2(8) = 2.9999999999999996。
詳細については、このstackoverflow Q/A: Math.log2 precision has changed in Chrome を参照してください。
これは、対数の結果をいつ下限または上限にするかを知ることができないことを意味します (または、丸め の前に既に 1 オフになっていることを簡単に予測できません)。

したがって、ループ内で入力数値が 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 53 ]でエラーはありません(同じ予測可能な丸め誤差で 最大 2 64です)。

または、他の (入力値が 32 ビットより大きい場合は繰り返し) bithacksを試すこともできます。

最も単純で最短の (ただし、上記の計算スニペットと比較すると遅くなる可能性があります) は、数値を文字列化し、結果の文字列の長さをAnuragの回答のようにカウントするreturn n && n.toString(2).length;ことです。ビット）。

于 2016-05-28T03:05:27.347 に答える
1

ビットが変化するそれぞれの境界でルックアップ テーブルを作成します。大きな値に対してのみこれを行うことができ、対数を通してより小さな値を行うことができます。ここでもPowerShellで再現できるので、一般的に浮動小数点関連のようです。

于 2010-06-20T23:23:22.530 に答える