Interessanter Algorithmus

[Interessierter (Gast)]

Da es sich um eine allgemeine Frage zu einem Algorithmus handelt, bin 
ich hier vielleicht falsch. Dann bitte verschieben, Mods.

------

In diesem Code 
http://bits.stephan-brumme.com/roundUpToNextPowerOfTwo.html und in 
diesem Code 
http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i 
erscheint eine bestimmte Abfolge von Ausdrücken.

  // Für 8-Bit Argumente
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);  // 16-Bit Argumente
   x = x | (x >> 16);  // 32-Bit Argumente etcpp.

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.

Faszinierend, wenn man (ich) solche Schemata finde. Ich möchte gerne 
darüber diskutieren.


Kennt jemand noch andere Verwendungszwecke dieser Abfolge?
Mag jemand etwas zum Hintergrund erzählen? Kann jemand Bemerkungen zum 
mathematischen Hintergrund hinzufügen?

Aus Symmetrieüberlegungen heraus, kann man die Folge umdrehen und nach 
links schieben. Gibt es dafür Verwendungen?

[Stephan B. (matrixstorm)]

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

[Karl H. (kbuchegg)]

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

  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.

  001x xxxx    ->  0001 xxxx

weden die beiden Zahlen miteinander verodert

  001x xxxx
| 0001 xxxx
------------
  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

  0011 xxxx    ->  0000 11xx


  0011 xxxx
| 0000 11xx
------------
  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

  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

   0000 0001       1
   0000 0010       2
   0000 0100       4
   0000 1000       8
   0001 0000      16
  ....

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

   0000 0001       1      0000 0000    0
   0000 0010       2      0000 0001    1
   0000 0100       4      0000 0011    3
   0000 1000       8      0000 0111    7
   0001 0000      16      0000 1111   15
   0010 0000      32      0001 1111   31
   0100 0000      64      0011 1111   63
   1000 0000     128      0111 1111  127
 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.

[(prx) A. K. (prx)]

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.

[Stephan B. (matrixstorm)]

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)

[(prx) A. K. (prx)]

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 (Gast)]

@ Karl Heinz

Ja. Witzig. Und sehr schöne Erklärung.
Wenn man vorher 1 subtrahiert, dann kriegt man auch den Eingangswert 
zurück, wenn x selbst schon eine Zweier-Potenz war und nicht die nächst 
höhere.

Ich habe die Sequenz verwendet um das MSB eines Wortes zu ermitteln.
Nehme ich mal Dein Zwischenergebnis von oben, bei dem durch die 
Schiebeoperationen und die Oder-Verknüpfung aus

001x xxxx

das hier

0011 1111

geworden ist, dann ergibt sich durch eine weitere Verschiebung nach 
rechts um ein Bit,

0001 1111

Negation aller Bits

1110 0000

und eine Und-Verknüpfung, mit dem Zwischenergebnis

0011 1111 UND
1110 0000 
---------
0010 0000

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

[Karl H. (kbuchegg)]

Interessierter schrieb:

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

> 0011 1111 UND
> 1110 0000
> ---------
> 0010 0000
>

>
> 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.

[(prx) A. K. (prx)]

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

Eine Addition von 1 hätte es nicht getan?

[Karl H. (kbuchegg)]

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)

[(prx) A. K. (prx)]

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)

[(prx) A. K. (prx)]

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.

[Interessierter (Gast)]

Karl Heinz schrieb:

> Ach lass ihm doch die Freude.

Naja. Nicht nur mir. Die Idee ist nicht von mir - leider.

> Ich denke, da gibt es nur wenig mathematischen "Hintergrund". Das hat
> jemand durch Betrachten von Bits irgendwann mal rausgefunden.

Ich denke, das ist plausibel. Vielleicht können wir ja hier mal ein 
bisschen mit ein paar Formeln spielen. Ich überlege schon ob es 
irgendeine geschlossene Form (ohne Fallunterscheidungen oder floor, 
ceil, Ganzzahlanteil etc.) mit Polynomen gibt. Bisher ohne Erfolg.