Zur nächsten Zweierpotenz aufrunden und davon Logarithmus berechnen

[Der Progger]

Hi,

gibt es eine schnelle Möglichkeit von einem vorzeichenlosen Integer die nächsthöhere Zweierpotenz zu bestimmen und davon den Logarithmus? Bzw. den Logarithmus der nächsthöheren Zweierpotenz?

[knivil]

1.) Ja, Position des hoechstwertigen/niedrigstes Bit herausfinden, dann sooft die 1 in die 0 shiften, wenn niedrigstes gesetzte Bit mit dem obersten nicht identisch ist, einmal mehr schiften -> fertig gerundet
2.) Logarithums zu welcher Basis?

[u_ser-l]

test, ob eine Zahl n>0 bereits Zweierpotenz ist:

n & (n-1) = 0 <=> n ist Zweierpotenz

Berechnung des (aufgerundeten) Logarithmus von n>0:

Falls n Zweierpotenz: Ausgabe der Bitposition der "1"

Falls nicht: suche die Stelle s (gezählt von 0 ab) der höchstwertigen "1" im Bitmuster von n und gib aus: s+1

[Michael E.]

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

[Der Progger]

Hi,

danke schonmal, dann werd ich wohl doch zu dem einfachen Weg greifen:

Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way) 
unsigned int v; // 32-bit word to find the log base 2 of
unsigned r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed...
{
  r++;
}
The log base 2 of an integer is the same as the position of the highest bit set (or most significant bit set, MSB). The following log base 2 methods are faster than this one.

Wollte nur sicher gehen, dass es nicht doch in einem Ausdruck geht (ohne Lookup-Table).

[DocShoe]

Kannst du nicht einfach den Logarithmus von n auf die nächste ganze Zahl aufrunden?

[knivil]

Es gibt die Assemblerbefehle bsf und bsr fuer x86.

[Michael E.]

DocShoe schrieb:

Kannst du nicht einfach den Logarithmus von n auf die nächste ganze Zahl aufrunden?

Viel zu langsam. Es wird etwas präzise berechnet, was mein eigentlich gar nicht braucht.

[rapso]

knivil schrieb:

Es gibt die Assemblerbefehle bsf und bsr fuer x86.

sehe ich auch als beste moeglichkeit auf x86, bzw POPCNT.

andere CPUs erlauben es z.b. mit je 8bit auf ein array zu indizieren und wenn man dann 4 werte hat, das maximum von denen zu erhalten, im pseudocode
Bit=HorizontalMax(PopCnt24[n>>24]|PopCnt16[(n>>16)&0xff)|...);
die instruktion ist meist nur als SIMD version vorhanden.