Höchste Binärstelle einer Zahl

Caipi

Soetwas habe ich heute auch gedacht :). (Ohne Garantie)
Gegeben sei deine Zahl x, deren höchste Binärstelle du finden möchtest.
Dann bekommst du mit n = log₂(x) eine Zahl deren Nachkommastellen du eventuell abschneidest. Fertig. 2ⁿ ist nun ≤ x.

Beispiel:
x = 9.
n = log₂(9) = 3.168825... | Kommastellen abschneiden.
n = 3.

Die höchste binäre Stelle der Zahl ist die 3.

Bin mir nicht sicher, ob das so korrekt ist. (Hab mir das jetzt alles so mehr oder weniger ausgedacht...). Aber ist ja auch nur ein Ansatz.

Caipi

Tja, aufwändig oder performant, du musst dich entscheiden

Wobei Wallis Weg ja nicht sonderlich kompliziert klingt.
Ich hätte da noch etwas mit ganzzahlgerundeten-2'er-Logarithmen anzubieten, wenn dir das lieber ist...

EDIT:
Ach Caipi hat ja auch schon gepostet, so machts keinen Spaß

dali

aufwändig oder performant

???

dali schrieb:

aufwändig oder performant

???

Umsonst ist nur der Tod, und der kost das Leben.

volkard

a) gute lösung: schau mal, was der assembler-befehl BSR macht. schreib eine zeile inline-asm. und gut ist's.

b) schlechte lösung: binäre suche.

c) katastrophische lösung:

u32 findLastBitTrue(u32 x){
	int result=0;
	while(x){
		x>>=1;
		++result;
	}
	return result;
}

naja, ich verwende c).

energyzer

@SeppSchrot: Mit Aufwand meinte ich Performance Zu faul, um eine Schleife
zu schreiben bin ich dann doch nicht...

Also die Lösung müsste schon _sehr_ schnell sein, sonst kann ich meinen
Algorithmus auch mit unbekannter Anzahl an Stellen schreiben... Ich
vermute mal log dürfte da zu unperformant sein.

// Edit: Danke volkard

groovemaster

Nunja, die shift-Variante könnte man evtl. mit 'ner LUT (zB für 8 Bits) noch etwas beschleunigen. Ob das allerdings schneller als der Assembler Befehl ist, darf bezweifelt werden.

evilissimo

groovemaster schrieb:

Nunja, die shift-Variante könnte man evtl. mit 'ner LUT (zB für 8 Bits) noch etwas beschleunigen. Ob das allerdings schneller als der Assembler Befehl ist, darf bezweifelt werden.

Und was soll das bringen? ( Das mit den 8 Bits, wenn er theoretisch jedes testen müsste )

ZuK

Habe folgendes mal irgendwo gefunden.

int highest_bit_idx(unsigned long x) {
    if ( 0==x )  return  0;
    unsigned long r = 0;
    if ( x & 0xffff0000 )  { x >>= 16;  r += 16; }
    if ( x & 0x0000ff00 )  { x >>=  8;  r +=  8; }
    if ( x & 0x000000f0 )  { x >>=  4;  r +=  4; }
    if ( x & 0x0000000c )  { x >>=  2;  r +=  2; }
    if ( x & 0x00000002 )  {            r +=  1; }
    return r+1;
}

Kurt

groovemaster

evilissimo schrieb:

Und was soll das bringen? ( Das mit den 8 Bits, wenn er theoretisch jedes testen müsste )

Du hast dann zB bei 'ner 32 Bit Zahl nicht maximal 32 Tests, sondern nur 4.

evilissimo

ach egal.