Zahl bitweise spreizen

[Schrompf]

Moin,

ich habe die Frage jetzt ein paar gelöscht, um sie jetzt doch mal zu Ende zu tippen und abzuschicken. Ich suche eine einfache Möglichkeit, eine Zahl bitweise zu spreizen. Also aus der Bitfolge

000000000000JKLM

will ich bekommen

000000000J0K0L0M

oder gern auch

0000 00J0 0K00 L00M

Nach meinem Verständnis kommt das einer Potenzierung gleich, aber mir fällt keine einfache Operation ein, das hinzubekommen, ohne die Bits zu vereinzeln und zurechtzuschieben.

Hintergrund: wenn man ein 2D- oder 3D-Array nicht banal zeilen- und schichtenweise linearisiert, sondern räumlich lokale Bereiche auch im Speicher lokal haben will, bekommt man solche Rechenschritte. Ich würde zum Beispiel gern einen 16x16x16-Cluster speichern, indem ich die 8 Subcluster von je 8x8x8 Größe hintereinander speichere, und jeden 8x8x8-Cluster wieder als 8 4x4x4-Cluster, usw. Wenn ich also aus einem XYZ-Index einen Arrayindex berechnen will, muss ich die Bits der drei Größen genau so interleaven wie im letzten Beispiel oben. Und daher suche ich eine schnelle Bit-Operation, um die Bits einer Zahl so zu spreizen.

[Alexander Kornrumpf]

Nach meinem Verständnis kommt das einer Potenzierung gleich, aber mir fällt keine einfache Operation ein, das hinzubekommen, ohne die Bits zu vereinzeln und zurechtzuschieben.

Ja wie willst du auch die Bits einzeln zurechtschieben, ohne sie einzeln zurechtzuschieben?

EDIT: Musste nochmal nachdenken:

du brauchst 4 AND 4 SHIFT und 4 OR um das hinzubekommen, oder? Wieviel besser soll es noch gehen?

[dot]

Es gibt iirc SSE2 Instructions die den Inhalt zweier Register interleaven können. Ansonsten würd ich das auf die Schnelle wohl einfach mit ein bisschen Bitgeschubse erledigen...

[CodingCat]

Das was du da generieren willst nennt sich Morton Code (mehrere Zahlen bit-interleaved, z.B. um Positionen in Cache-freundliches Z-order/morton-order Layout zu sortieren). Für Encoding & Decoding ohne spezielle Instruktionen klicke hier.

[Schrompf]

Morton Code! Ein Stichwort zum Belesen! Danke.

Bitgeschubse geht natürlich immer. Aber da bräuchte ich pro Bit und pro Teilnehmer mindestens ein AND und ein Shift. Ich dachte, ich frage mal, ob es was Besseres als das gibt.

[CodingCat]

Bitgeschubse geht natürlich immer. Aber da bräuchte ich pro Bit und pro Teilnehmer mindestens ein AND und ein Shift. Ich dachte, ich frage mal, ob es was Besseres als das gibt.

Siehe Link, für 16 Bits brauchst du 4 Ands und 4 Shifts pro Teilnehmer, fortgesetzt für 32 Bits jeweils nur eine Operation mehr.

[Schrompf]

Siehe Link, für 16 Bits brauchst du 4 Ands und 4 Shifts pro Teilnehmer, fortgesetzt für 32 Bits jeweils nur eine Operation mehr.

Ich weiß! Daher mein "Danke" :-)

[CodingCat]

OK, wollte nur sichergehen, dass du das gefunden hast. :)

[BeRsErKeR]

Wenn es vom Code her kürzer sein soll:

Code: Alles auswählen

int result = 0;
for (int i = 0; i < n; ++i)
{
    int val = (bits & (1 << i)) << 1;
    result += val * val;
}
result >>= 1;

Damit machst du z.B. aus "00001111" -> "10101010".

Wenn du "01010101" haben willst musst du halt result >>= 2; schreiben. ;)

n gibt die Anzahl der Bits an die du berücksichtigen willst. Im Beispiel z.B. 4.


Prinzipiell ist das Ergebnis Bit0 * 2 + Bit1 * 4 + Bit2 * 8 + ...
Wenn die Bits gesetzt sind also quasi 1 * 2 + 2 * 4 + 4 * 8 + ...
Zur Einfachheit verdopple ich die Bit-Werte, sodass ich Potenzen nutzen kann: 2 * 2 + 4 * 4 + 8 * 8 + ... bzw. Bit0 * 2 + Bit1 * 4 + Bit2 * 8 + ...
Dann muss man am Ende das Ergebnis nur wieder durch 2 teilen und hat das Ergebnis. So hab ichs im Beispiel gemacht.

[Krishty]

Ich schätze, Leistung ist ihm gerade wichtiger als deutlicher Quelltext. Außerdem: unsigned bei Bitgeschichten! ;)

[BeRsErKeR]

Ich schätze, Leistung ist ihm gerade wichtiger als deutlicher Quelltext. Außerdem: unsigned bei Bitgeschichten! ;)

Das war eben zum Test reingehackt. unsigned ist schon klar. ;)
Übrigens kann man das Beispiel vielleicht auch auf relativ einfache Bitoperationen reduzieren.

[dot]

Evtl. auch interessant: http://graphics.stanford.edu/~seander/b ... ve64bitOps ;)

[BeRsErKeR]

Evtl. auch interessant: http://graphics.stanford.edu/~seander/b ... ve64bitOps ;)

Wirklich sehr interessant. Auf Schrompfs Beispiel bezogen kann er das dann einfach mit folgendem Code machen:

Code: Alles auswählen

unsigned int bits = 15; // should be lower than 2^16
bits = (bits | (bits << 8)) & 0x00FF00FF;
bits = (bits | (bits << 4)) & 0x0F0F0F0F;
bits = (bits | (bits << 2)) & 0x33333333;
bits = (bits | (bits << 1)) & 0x55555555;

[Krishty]

Hm? Bezog sich dot nicht eher darauf, das via Multiplikation zu lösen?

[Schrompf]

Aber sehr coole Seite, die Du da verlinkt hast, dot! Danke, die speichere ich mir gleich mal.

Aus meinem Bauchgefühl heraus sollte das in bestenfalls O(log n) mit n als Bitanzahl möglich sein. Aber vielleicht hätte es dafür ja auch eine Intrinsic Function gegeben... ich hatte da Hoffnung, nachdem ich jetzt _BitScanForward und _BitScanReverse für mich entdeckt habe. Aber nuja, die Bit Twiddling Hacks sind auch sehr cool.

[dot]

Mich wundert ja, wieso ich die Seite nicht gleich verlinkt hab; mein Problem war wohl dass ich bei deinem Beispiel sofort die Ziffern einer Zahl in Hex gesehen und an Nibbles gedacht hab und das Wort "Bitfolge" irgendwie an meinem Hirn vorbeigezogen ist. ^^
Über ein entsprechendes Intrinsic wär ich noch nicht gestolpert, die SSE2 Instructions an die ich gedacht hab, können nur ganze Bytes interleaven, nicht einzelne Bits.

Aber rein prinzipiell brauchst du ja eigentlich einfach nur die geraden und ungeraden Bits beider Operanden maskieren und entsprechend geshiftet zusammen ORen, was ja wohl genau ist, was der bereits gepostete Beispielcode macht...