ビット数を増やす効率的な条件式

Question

符号なし整数のシーケンスが増えているとします。C[i]彼らが増加するにつれ、彼らはますます多くのビットを占有する可能性が高いです。私は、シーケンスC[i]とC[i+1]の2つの連続した要素（過去と未来は観測できません）に基づいた効率的な条件付きを探しています。これは、必要なビット数が増えるたびに正確にまたはほぼ1回評価されます。条件付きの

明らかに（しかし遅い）選択肢は次のとおりです。

if (ceil(log(C[i+1])) > ceil(log(C[i]))) ... 

と同様に（より良いまだ大きくない）特殊なCPUのオペコードを使用して、先行ゼロのビットの数を計算何でも。

ちょうどビットごとまたはビットごとに値を使用し、値がC[i+1]およびC[i]のniceソリューションがあると思われます。何かご意見は？

Answer 1

は、あなたの二つの数は、xとyいると仮定します。それらが同じ高位ビットを有する場合、x^yはxとyの両方よりも小さい。そうでなければ、2つのうちの1つよりも高い。

だから

v = x^y 
if (v > x || v > y) { ...one more bit... } 

Answer 2

値が2の累乗をオーバーフローしようとすると、ビット数が増加します。 簡単なテストは次のようになります。

while (C[i] >= (1<<number_of_bits)) then number_of_bits++; 

あなたはそれがさらに高速化したい場合：

int number_of_bits = 1; 
int two_to_number_of_bits = 1<<number_of_bits ; 


... your code .... 

while (C[i]>=two_to_number_of_bits) 
    { number_of_bits++; 
    two_to_number_of_bits = 1<<number_of_bits ; 
    } 

Answer 3

私はあなただけをリードカウント」（clzは、先行ゼロの数を返す関数であるclz(C[i+1]) < clz(C[i])が必要だと思いますゼロ "）。いくつかのCPUファミリには、これを実行するための命令があります（これは、イントリンシックとして利用可能です）。そうでない場合は、自分でロールを張らなければなりません（通常、いくつかの手順が必要です）。Hacker's Delightを参照してください。

Answer 4

値がオーバーフローして2の累乗になると、ビット数が増加します。簡単なテストでは、値は2の累乗 - 1に等しいか？

if ((C[i] & (C[i]+1))==0) ... 

Answer 5

を考えると（私はこれがHacker's Delightから来ていると信じて）：：

int hibit(unsigned int n) { 
    n |= (n >> 1); 
    n |= (n >> 2); 
    n |= (n >> 4); 
    n |= (n >> 8); 
    n |= (n >> 16); 
    return n - (n >> 1); 
} 

あなたの条件は、単にhibit(C[i]) != hibit(C[i+1])でこれが尋ねることによって達成することができます。

Answer 6

BSR - ビットスキャンリバース（386+）

Usage: BSR  dest,src 
    Modifies flags: ZF 

    Scans source operand for first bit set. Sets ZF if a bit is found 
    set and loads the destination with an index to first set bit. Clears 
    ZF is no bits are found set. BSF scans forward across bit pattern 
    (0-n) while BSR scans in reverse (n-0). 

          Clocks     Size 
    Operands   808x 286 386 486   Bytes 

    reg,reg   -  - 10+3n 6-103   3 
    reg,mem   -  - 10+3n 7-104   3-7 
    reg32,reg32  -  - 10+3n 6-103   3-7 
    reg32,mem32  -  - 10+3n 7-104   3-7 

あなたは（Cの[i]とC [i]の1）これらのうちの2つを必要と比較します。

Answer 7

キース・ランダルの解法は良いですが、O（w + n）命令のシーケンス全体を処理する次のコードを使って1つのxor命令を保存できます.wはワードのビット数、nはシーケンス内の要素の数シーケンスが長い場合、ほとんどの反復は1つのxor命令を避けて1回の比較のみを行います。

これは、次のように達している2の最高出力を追跡することによって達成される：

t = 1; // original setting 

if (c[i + 1] >= t) { 
    do { 
    t <<= 1; 
    } while (c[i + 1] >= t); // watch for overflow 
    ... // conditional code here 
}