Interessanter Algorithmus

Aufrunden auf 2^(1+floor(ld(x)))-1 ?

Mit x als Eingabewert und ld() den Logarithmus zur Basis 2 
(ln(x)/ln(2)).

Kann man gebrauchen um Bitmasken zu berechnen...

MfG

Interessierter schrieb:

> Ich würde die Wirkung etwa so zusammenfassen:
> Das jeweilige Bit k (0 bis n-1 eines n-Bit Wortes), ist 0 wenn jedes der
> Bits von k bis n-1 Null ist bzw. es ist Eins wenn irgendeines der Bits
> Eins ist.

Ich würde die Arbeitsweise so zusammenfassen.

Gegeben irgendein 8 Bit Wert

1

  001x xxxx

wobei uns die mit x markierten Bits nicht wirklich interessieren. Warum 
wird gleich klar.

Man nehme diesen Wert und verschiebe ihn um 1 Stelle nach rechts.

1

  001x xxxx    ->  0001 xxxx

weden die beiden Zahlen miteinander verodert

1

  001x xxxx

2

| 0001 xxxx

3

------------

4

  0011 xxxx

dann entsteht ein Ergebnis, bei dem sich das am weitesten links sitzende 
1 Bit auf jeden Fall nach rechts dupliziert hat.


Das ganze nochmals, diesmal aber mit einer Verschiebung um 2 Stellen

1

  0011 xxxx    ->  0000 11xx

2

3

4

  0011 xxxx

5

| 0000 11xx

6

------------

7

  0011 11xx

Aus den 2 Stück 1 Bits sind jetzt schon 4 geworden.

Mit jeder Wiederholung des Prozesses (und Verdopplung der 
Schiebedistanz, verdoppelt sich auch die Anzahl der garantierten 1 Bits.

Bis man letzten Endes, in diesem Beispiel bei

1

  0011 1111

landet. Die am weitesten links stehende 1 wurde nach rechts dupliziert, 
bis rechts von ihr nur 1 Bits stehen.

Dazu jetzt noch die Beobachtung in den Binärzahlen, dass alle 2-er 
Potenzen ausschliesslich ein einzelnes 1 Bit haben

1

   0000 0001       1

2

   0000 0010       2

3

   0000 0100       4

4

   0000 1000       8

5

   0001 0000      16

6

  ....

und die jeweils um 1 kleinere Zahl aus lauter 1 Bits besteht, die rechts 
vom 1-Bit der 'zugehörenden' 2-er Potenz stehen

1

   0000 0001       1      0000 0000    0

2

   0000 0010       2      0000 0001    1

3

   0000 0100       4      0000 0011    3

4

   0000 1000       8      0000 0111    7

5

   0001 0000      16      0000 1111   15

6

   0010 0000      32      0001 1111   31

7

   0100 0000      64      0011 1111   63

8

   1000 0000     128      0111 1111  127

9

 1 0000 0000     256      1111 1111  255

ist klar, wie es dann weiter geht. Nach der Verschiebeorgie noch 1 
dazuzählen und du hast die aufgerundete 2-er Potenz die zu der Zahl mit 
dem 1 Bit an der (beliebigen) höchsten Stelle steht.

Wobei mit GCC ausgestattete faule Zeitgenossen die Funktion 
"__builtin_clz" verwenden und sich damit die Mühe ersparen, die für den 
jeweiligen Prozessor sinnvollste Sequenz rauszukriegen.

Viele Prozessoren haben das für Wortbreite in Hardware gegossen, die 
besseren Cortexe eingeschlossen, und im Gegensatz zu dem, was im anfangs 
verlinkten Thread behauptet wird, hat BSR in den x86ern der letzten 2 
Jahrzehnte meist eine feste Laufzeit. AVRs wiederum tun sich mit Shifts 
etwas schwer und bevorzugen daher andere Varianten.

A. K. schrieb:
> Wobei mit GCC ausgestattete faule Zeitgenossen die Funktion
> "__builtin_clz" verwenden und sich damit die Mühe ersparen, die für den
> jeweiligen Prozessor sinnvollste Sequenz rauszukriegen.

Sicher das das noch das selbe macht?:

— Built-in Function: int __builtin_clz (unsigned int x)

    Returns the number of leading 0-bits in x, starting at the most 
significant bit position. If x is 0, the result is undefined.


Nachtrag:
Du meinst dann sicher sowas hier:(1<<(n-__builtin_clz(x)))-1  ??
(Fuer x!=0 ...natuerlich)

Stephan B. schrieb:
> Sicher das das noch das selbe macht?:

Es geht ja letztlich darum, die Nummer des höchsten gesetzten Bits 
rauszukriegen. Und die ist
    NumberOfBits-1 - __builtin_clz(x)

Macht sich beispielweise in priority queues ganz gut, z.B. in einem 
RTOS.

Interessierter schrieb:

> und eine Und-Verknüpfung, mit dem Zwischenergebnis
>
>

1

> 0011 1111 UND

2

> 1110 0000

3

> ---------

4

> 0010 0000

5

>

>
> ein Wert der dem höchsten im Eingangswert gesetzten Bit entspricht.

Clever

Um auf eine FRage im Eröffnungsposting einzugehen
> Kann jemand Bemerkungen zum mathematischen Hintergrund hinzufügen?
Ich denke, da gibt es nur wenig mathematischen "Hintergrund". Das hat 
jemand durch Betrachten von Bits irgendwann mal rausgefunden. Ich bin 
davon überzeugt, dass derartige 'Hacks'(*) einfach durch Spielen auf dem 
Papier gefunden wurden.

(*) Hack im ursprünglichen Wortsinn. Ein Hack war früher eine clevere 
Lösung. Ein Hacker war derjenige, der mit einer cleveren Lösung 
hochgekommen ist. Die negative Bedeutung hat das Wort Hacker erst viel 
später bekommen.

Interessierter schrieb:
> Negation aller Bits
> und eine Und-Verknüpfung, mit dem Zwischenergebnis

Eine Addition von 1 hätte es nicht getan?

A. K. schrieb:
> Interessierter schrieb:
>> Negation aller Bits
>> und eine Und-Verknüpfung, mit dem Zwischenergebnis
>
> Eine Addition von 1 hätte es nicht getan?

Ach lass ihm doch die Freude.
1 addieren und 1 mal rechts schieben um genau zu sein.

Aber dann gibt es wieder den lausigen Sonderfall des gesetzten Bit 7, 
welches zu einem 'Overflow' nach Bit 8 führt und wieder sonderbehandelt 
werden muss. Das spart er sich.
(Noch mal drüber nachgedacht. Das würde in Assembler das Carry Flag 
leicht erledigen können. Aber hier ist ja C)

Stephan B. schrieb:
> Du meinst dann sicher sowas hier:(1<<(n-__builtin_clz(x)))-1  ??

Fast. Für 32 Bits eher (1U<<31) >> __builtin_clz(x)

Karl Heinz schrieb:
> Aber dann gibt es wieder den lausigen Sonderfall des gesetzten Bit 7,

Nö. Vorher 1 rechts schieben, wie er getan hat, darf schon sein. Nur das 
abschliessende NEG+AND wird durch INC ersetzt.