Effiziente Bedingung für zunehmende Größe in Bits

Question

Angenommen, ich habe eine ansteigende Sequenz von Ganzzahlen ohne Vorzeichen C[i]. Wenn sie zunehmen, werden sie wahrscheinlich immer mehr Bits einnehmen. Ich suche nach einer effizienten Bedingung, basierend auf zwei aufeinander folgenden Elementen der Sequenz C[i] und C[i+1] (Vergangenheit und Zukunft sind nicht beobachtbar), die wahr entweder genau oder ungefähr einmal für jedes Mal evaluieren wird, wenn die Anzahl der erforderlichen Bits zunimmt .

Eine offensichtliche (aber langsam) Wahl der bedingt ist:

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

und ebenfalls alles, was die Anzahl von führenden Null-Bits mit speziellem CPU-Opcodes (viel besser, aber immer noch nicht gut) berechnet.

Ich vermute, es kann eine schöne Lösung mit einem Ausdruck nur bitweise oder und bitweise und auf die Werte C[i+1] und C[i]. Irgendwelche Gedanken?

Answer 1

Angenommen, Ihre beiden Zahlen sind x und y. Wenn sie das gleiche Bit höherer Ordnung haben, dann ist x^y kleiner als sowohl x als auch y. Ansonsten ist es höher als einer der beiden.

So

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

Answer 2

Die Anzahl der Bits erhöht sich, wenn der Wert eine Zweierpotenz überschreitet. Ein einfacher Test ist dann:

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

Wenn Sie es noch schneller wollen:

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

Ich glaube, Sie clz(C[i+1]) < clz(C[i]) nur brauchen, wo clz ist eine Funktion, die die Anzahl der führenden Nullen zurückgibt ("zählen führende Nullen "). Einige CPU-Familien haben dafür eine Anweisung (die möglicherweise als Instrinsic verfügbar ist). Wenn nicht, müssen Sie Ihre eigenen rollen (es dauert in der Regel nur ein paar Anweisungen) - siehe Hacker's Delight.

Answer 4

Die Anzahl der Bits geht nach oben, wenn der Wert über dem Überlauf eine Zweierpotenz ist. Ein einfacher Test ist dann, ist der Wert gleich einer Potenz von zwei, minus 1? Dies kann mit der Frage erreicht werden:

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

Answer 5

Given (Ich glaube, das von Hacker's Delight kommt):

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

Ihre bedingt ist einfach hibit(C[i]) != hibit(C[i+1]).

Answer 6

BSR - Bit Scan umge (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 

Sie müssen zwei davon (auf C [i] und C [i] + 1) und einem vergleichen.

Answer 7

Keith Randalls Lösung ist gut, aber Sie können einen xor-Befehl speichern, indem Sie den folgenden Code verwenden, der die gesamte Sequenz in O (w + n) -Anweisungen verarbeitet, wobei w die Anzahl der Bits in einem Wort und n ist die Anzahl der Elemente in der Sequenz. Wenn die Sequenz lang ist, beinhalten die meisten Iterationen nur einen Vergleich, wobei ein xor-Befehl vermieden wird.

Dies wird durch Verfolgen der höchsten Potenz von zwei erreicht, die wie folgt erreicht:

t = 1; // original setting 

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