7

私はバイナリで右端のビットのものを分離することについて検索していました:

そして、私はこの解決策を得ました:

y = x & (-x)

それで ：

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

しかし今、私は左端の桁を見つけることによって数値の大きさを見つけたいと思っています（ただし、符号ではありません...）

最も左のビットを見つけるために私の解決策を詳しく説明するにはどうすればよいですか?

例:

10 111100

0 1000100

4

2 に答える 2

4

数値の大きさを見つけるための同様の O(1) ビット単位のトリックはありません。多くのマイクロプロセッサ命令セットには、「先頭のゼロをカウントする」ための特別な命令が含まれています。C 言語ファミリには、JavaScript にビット単位の機能を与えるような演算子はありません。

O(1) の唯一の代替手段はMath.floor( Math.log( n ) / Math.LN2 )、

for ( var i = 0; i == Math.floor( Math.log( 1<<i ) / Math.LN2 ); ++ i ) ;

演算子が 32 ビットの 2 の補数の符号付き算術演算を使用i == 31しているため、結果として が得られます。<<

純粋主義者になりたい場合は、O( log n) である 1 だけ繰り返し右シフトするか16 >> i、i0 から 4 まで繰り返し右シフトして、結果が 0 の場合はシフトを拒否し、それ以外の場合は を累積し16 >> iます。これは O(log log N) です。ここで、N は の最大値でnあり、一定の時間を意味しますが、すべての確率で よりも遅くなりMath.logます。

O( log log N ) アルゴリズムのコード:

var mag = function( n ) {
     var acc = 0;
     for ( var i = 16; i; i >>= 1 ) {
         if ( n >> i ) {
             n >>= i;
             acc += i;
         }
     }
     return acc;
};

もちろん、これらのいずれについても、インデックスではなく「左端の 1 ビット」を取得するために、結果を 1 つ左にシフトする必要があります。

編集:logベースの実装は-Infinity0 を返しますが、関数magは を返しますが0、これは の結果と同じです1。最左端の 1 ビットが存在しない可能性を考慮したい場合は、特殊なケースにすることをお勧めします。

于 2013-01-25T12:26:05.540 に答える
2

Math.floor( Math.log( n ) / Math.LN2 )基本的な操作ではないため、それは O(1)ではないと思いますMath.log。

したがって、次の定理によれば、左端の 1 ビットを取得することはできません。「単語を単語にマッピングする関数は、命令の各ビットが結果は、各入力オペランドとその右側のビットのみに依存します。」

この定理は、「ハッカーの喜び」(Henry S. Warren, Jr.) の本の 13 ページにあります。

于 2016-04-01T08:05:05.890 に答える