Höchste Binärstelle einer Zahl

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.