Herausfinden, wie viele binäre Ziffern eine bestimmte ganze Zahl hat

Question

Mögliches Duplikat:
Berechnung der schnellen logarithmischen Basis-2-Obergrenze

Wie kann man am schnellsten herausfinden, wie viele Binärziffern eine bestimmte ganze Zahl hat, wenn sie in C/C++ von Dezimal- in Binärzahlen umgewandelt wird?

Ex. 47 ₍₁₀₎ \= 101111 ₍₂₎

47 hat also 6 Ziffern in binärer Darstellung.

Answer 1

Eine schnelle und unterhaltsame Methode, dies zu tun, ohne mathematische Funktionen aufrufen zu müssen, finden Sie hier:

for (digits = 0; val > 0; val >>= 1)
        digits++;

Als Bonus sollte dies zu einer Speicherbelastung und 2 Registern in Gebrauch, für zusätzliche whiz-bang kochen.

Answer 2

Wenn Sie nach dem "schnellsten" Weg in Bezug auf die Leistung suchen, müssen Sie auf plattformspezifische Methoden zurückgreifen.

Einige Architekturen haben sogar eine Anweisung, die das tut.

Auf x86 haben Sie die bsr Anweisung.

In MSVC ist sie zugänglich als:

inline int bitlength(unsigned long x){
    if (x == 0)
        return 0;

    unsigned long index;
    _BitScanReverse(&index,x);
    return (int)(index + 1);
}

GCC hat die __builtin_clz() immanent - die etwas Ähnliches tut.

Answer 3

Die schnellste Lösung, die unter meine Lieblingssammlung von Bit-Twisting-Hacks es Ermittlung der logarithmischen Basis 2 einer N-Bit-Ganzzahl in O(lg(N)) Operationen mit Multiplikation und Nachschlagen . Es sind 13 Anweisungen erforderlich, um das höchste gesetzte Bit einer Zahl zu finden.

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Answer 4

Der traditionelle Weg

int count = 32;
for(int i = 1 << 31; i != 0; i >>= 1, count--)
    if((number & i) != 0) return count;

Bei der Optimierung können Sie sich noch mehr einfallen lassen.

EDIT 2 Hier ist der schnellste Code, der mir einfiel, ohne die Verwendung des Bit Scan Reverse Opcodes. Sie könnten eine größere LUT (256 Einträge) verwenden und die letzte IF-Anweisung entfernen. In meinen Tests war dies schneller als die wiederholte OR-SHIFT dann LUT-Methode in einem anderen Beitrag beschrieben.

int[] Log2_LUT = new int[16]{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
int Log2 (number) {
int count = 0;
if((number & 0xFFFF0000) != 0) { 
    number >>= 16;
    count += 16;
}
if((number & 0x0000FF00) != 0) { 
    number >>= 8;
    count += 8
}
if((number & 0x000000F0) != 0) {
    number >>= 4;
    count += 4;
}
return count + Log2_LUT[number];
}

Bei einer x86- oder x86-64-Bit-Architektur können Sie auch den BSR-Opcode (Bit Scan Reverse) verwenden. Sie können die C++-Intrinsic dafür finden http://msdn.microsoft.com/en-us/library/fbxyd7zd%28v=vs.80%29.aspx

Auch Ihre Frage ist ähnlich wie diese Wie kann man am schnellsten die Anzahl der Bits berechnen, die zum Speichern einer Zahl benötigt werden?

EDITAR Warum die log2-Antworten nicht optimal sind... Obwohl mathematisch korrekt, sind komplexe Gleitkommaoperationen (Sinus, Kosinus, tan, log) die langsamsten Operationen auf modernen Computern. Hinzu kommt, dass eine ganze Zahl in eine Fließkommazahl umgewandelt werden muss und auch noch die Ober- und Untergrenze zu berechnen ist.

Answer 5

Versuchen Sie einen Logarithmus zur Basis 2:

ceil(log2(n))