Wie lg2 einer Reihe zu bekommen, die

Question

2^k Was ist die beste Lösung für das Erhalten der Basis 2 Logarithmus einer Zahl ist, die ich kenne, ist eine Zweierpotenz (2^k). (. Natürlich weiß ich nur den Wert 2^k nicht k selbst)

Ein Weg, dachte ich zu tun ist, um 1 subtrahiert wird und dann eine Bitcount tun:

lg2(n) = bitcount(n - 1) = k, iff k is an integer 
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4 

Aber gibt es einen schnelleren Weg, es zu tun (ohne Zwischenspeicherung)? Auch etwas, das keine Bitcount über so schnell beinhaltet, wäre schön zu wissen?

Eine der Anwendungen ist dies:

suppose you have bitmask 
0b0110111000 

and value 
0b0101010101 

and you are interested of 
(value & bitmask) >> number of zeros in front of bitmask 
(0b0101010101 & 0b0110111000) >> 3 = 0b100010 

this can be done with 

using bitcount 
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1 

or using lg2 
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1) - 2 

Denn es ist schneller als bitcount ohne Cachen es schneller als O(lg(k)) sein sollte, wo k ist die Anzahl der Speicherbits.

Answer 1

Viele Architekturen haben eine „finden erste“ Anweisung (BSR, clz, bfffo, cntlzw usw.), die viel schneller ist als Bit-Zählung Ansätze.

Answer 2

Wenn Sie wissen, dass die Zahl eine Potenz von 2 ist, können Sie sie einfach nach rechts verschieben (>>), bis sie gleich 0 ist. Wie oft Sie nach rechts verschoben haben (minus 1), ist k.

Bearbeiten: schneller als dies ist die Nachschlagetabelle Methode (obwohl Sie etwas Platz opfern, aber nicht eine Tonne). Siehe http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Answer 3

Wenn Sie nicht mit Schwimmern tun nichts dagegen können Sie log(x)/log(2) verwenden.

Answer 4

Ja. Hier ist eine Möglichkeit, es ohne die Bitcount in lg(n) zu tun, wenn Sie die ganze Zahl in Frage wissen, ist eine Potenz von 2.

unsigned int x = ...; 
static const unsigned int arr[] = { 
    // Each element in this array alternates a number of 1s equal to 
    // consecutive powers of two with an equal number of 0s. 
    0xAAAAAAAA, // 0b10101010..   // one 1, then one 0, ... 
    0xCCCCCCCC, // 0b11001100..   // two 1s, then two 0s, ... 
    0xF0F0F0F0, // 0b11110000..   // four 1s, then four 0s, ... 
    0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.] 
    0xFFFF0000 
} 

register unsigned int reg = (x & arr[0]) != 0; 
reg |= ((x & arr[4]) != 0) << 4; 
reg |= ((x & arr[3]) != 0) << 3; 
reg |= ((x & arr[2]) != 0) << 2; 
reg |= ((x & arr[1]) != 0) << 1; 

// reg now has the value of lg(x). 

In jedem der reg |= Schritte, wir nacheinander testen, ob eines der Bits von x werden mit abwechselnden Bitmasken in arr geteilt. Wenn sie sind, bedeutet das, dass lg(x) Bits, die in diesem bitmask sind, und wir effektiv 2^k-reg hinzufügen, wo k das Protokoll der Länge des Wechsel bitmask ist. Zum Beispiel ist 0xFF00FF00 eine alternierende Folge von 8 Einsen und Nullen, also k ist 3 (oder lg(8)) für diese Bitmaske.

Im Wesentlichen, jeder reg |= ((x & arr[k]) ... Schritt (und die anfängliche Zuordnung) testet, ob Bit k gesetzt hat. Wenn ja, fügen wir es zu reg hinzu; Die Summe all dieser Bits wird lg(x) sein.

, das wie eine Menge Magie aussieht, also lassen Sie uns ein Beispiel versuchen. Angenommen, wir wollen wissen, welche Kraft von 2 der Wert 2.048 ist:

// x = 2048 
// = 1000 0000 0000 

register unsigned int reg = (x & arr[0]) != 0; 
// reg =  1000 0000 0000 
     & ... 1010 1010 1010 
     =  1000 0000 0000 != 0 
// reg = 0x1 (1)  // <-- Matched! Add 2^0 to reg. 

reg |= ((x & arr[4]) != 0) << 4; 
// reg =  0x .. 0800 
      & 0x .. 0000 
     =    0 != 0 
// reg = reg | (0 << 4) // <--- No match. 
// reg = 0x1 | 0 
// reg remains 0x1. 

reg |= ((x & arr[3]) != 0) << 3; 
// reg =  0x .. 0800 
      & 0x .. FF00 
     =   800 != 0 
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg. 
// reg = 0x1 | 0x8 
// reg is now 0x9.   

reg |= ((x & arr[2]) != 0) << 2; 
// reg =  0x .. 0800 
      & 0x .. F0F0 
     =    0 != 0 
// reg = reg | (0 << 2) // <--- No match. 
// reg = 0x9 | 0 
// reg remains 0x9.   

reg |= ((x & arr[1]) != 0) << 1; 
// reg =  0x .. 0800 
      & 0x .. CCCC 
     =   800 != 0 
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg. 
// reg = 0x9 | 0x2 
// reg is now 0xb (11). 

Wir sehen, dass der Endwert reg ist 2^0 + 2^1 + 2^3, das in der Tat ist 11.