====== std.bits — Bitoperationen ======
Schieben und Rotieren mit vorhersagbarem Verhalten, Zählfunktionen über alle 64 Bit und Bitmengen beliebiger Größe mit Rank und Select.
→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:i128|std.i128]] · [[lyx_-_programmiersprache:units:math|std.math]] · [[lyx_-_programmiersprache:sprache:rohspeicher|Rohspeicher]]
import std.bits;
Keine Abhängigkeiten — ''std.bits'' ist Schicht 0 und kommt ohne jede andere Unit aus. 65 Funktionen, eine Konstante (''BITS_WORD'' = 64). Alle Beispiele dieser Seite sind mit ''lyxc 1.0.21A'' übersetzt und ausgeführt.
----
===== Warum nicht einfach ''%%<<%%'' und ''>>''? =====
Weil die Prozessorbefehle die Schiebeweite **modulo 64** nehmen. Das ist kein Fehler, sondern Hardware — aber es überrascht, sobald die Weite aus einer Rechnung stammt:
unit main;
import std.io;
import std.string;
import std.bits;
fn main(): int64 {
Print("roh 1 << 64 = "); PrintLn(IntToStr(1 << 64));
Print("BitsShl(1, 64) = "); PrintLn(IntToStr(BitsShl(1, 64)));
Print("roh 1 << 65 = "); PrintLn(IntToStr(1 << 65));
Print("BitsShl(1, 65) = "); PrintLn(IntToStr(BitsShl(1, 65)));
return 0;
}
roh 1 << 64 = 1
BitsShl(1, 64) = 0
roh 1 << 65 = 2
BitsShl(1, 65) = 0
**''1 %%<<%% 64'' ergibt 1**, weil 64 mod 64 = 0 ist. ''BitsShl'' **sättigt** stattdessen: alles ab Breite 64 ergibt 0, so wie es mathematisch sein muss. Wer die Schiebeweite nicht selbst in der Hand hat — aus einer Feldbreite, einer Konfiguration, einer Benutzereingabe —, nimmt die Funktionen.
^ Roh ^ ''std.bits'' ^ Unterschied ^
| ''a %%<<%% n'' | ''BitsShl(a, n)'' | sättigt statt modulo 64 |
| ''a >> n'' | ''BitsShr(a, n)'' | logisch (füllt Nullen), sättigt |
| – | ''BitsSar(a, n)'' | arithmetisch (füllt das Vorzeichenbit) |
| – | ''BitsShlChecked(a, n, ok)'' | meldet über ''ok'', ob Bits verlorengingen |
| – | ''BitsShlOverflows(a, n)'' | fragt dasselbe, ohne zu rechnen |
''BitsShr'' und ''BitsSar'' unterscheiden sich nur bei negativen Zahlen: ''BitsShr(−1, 1)'' schiebt eine Null nach und ergibt eine große positive Zahl, ''BitsSar(−1, 1)'' bleibt bei −1.
----
===== Zählen und Suchen =====
unit main;
import std.io;
import std.string;
import std.bits;
fn Z(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn main(): int64 {
Z("PopCount(-1) = ", BitsPopCount(-1));
Z("PopCount(255) = ", BitsPopCount(255));
Z("Clz(1) = ", BitsClz(1));
Z("Ctz(8) = ", BitsCtz(8));
Z("Extract(0xFF, 4, 4) = ", BitsExtract(255, 4, 4));
Z("Reverse(1) = ", BitsReverse(1));
Z("SwapBytes(1) = ", BitsSwapBytes(1));
Z("CeilPow2(100) = ", BitsCeilPow2(100));
return 0;
}
PopCount(-1) = 64
PopCount(255) = 8
Clz(1) = 63
Ctz(8) = 3
Extract(0xFF, 4, 4) = 15
Reverse(1) = -9223372036854775808
SwapBytes(1) = 72057594037927936
CeilPow2(100) = 128
Die beiden auffälligen Zeilen sind richtig: ''BitsReverse(1)'' schiebt Bit 0 auf Bit 63 — das ist als ''int64'' gelesen −2⁶³. ''BitsSwapBytes(1)'' macht aus dem niedrigsten Byte das höchste, also 2⁵⁶.
^ Funktion ^ Liefert ^
| ''BitsPopCount(x)'' | Anzahl gesetzter Bits (SWAR über alle 64 Bit) |
| ''BitsParity(x)'' | 1 bei ungerader Anzahl, sonst 0 |
| ''BitsClz(x)'' / ''BitsCtz(x)'' | führende / nachlaufende Nullen |
| ''BitsHighestSet(x)'' / ''BitsLowestSet(x)'' | Index des höchsten / niedrigsten gesetzten Bits |
| ''BitsHamming(a, b)'' | Anzahl unterschiedlicher Bits |
| ''BitsTest/Set/Clear/Toggle(x, i)'' | einzelnes Bit lesen und setzen |
| ''BitsExtract(x, pos, len)'' | Bitfeld herausziehen |
| ''BitsDeposit(x, pos, len, v)'' | Bitfeld einsetzen |
| ''BitsIsPow2'' · ''BitsFloorPow2'' · ''BitsCeilPow2'' | Zweierpotenzen |
| ''BitsGrayEncode'' / ''BitsGrayDecode'' | Gray-Code hin und zurück |
----
===== Rotation in beliebiger Breite =====
Das ist der Teil, den der Bestand nicht hat. ''BitsRotlN(x, n, width)'' rotiert innerhalb einer **frei gewählten** Breite; die gängigen Breiten gibt es als fertige Namen:
^ Funktion ^ Breite ^
| ''BitsRotl'' / ''BitsRotr'' | 64 |
| ''BitsRotl32'' / ''BitsRotr32'' | 32 |
| ''BitsRotl16'' / ''BitsRotr16'' | 16 |
| ''BitsRotl8'' / ''BitsRotr8'' | 8 |
| ''BitsRotlN'' / ''BitsRotrN'' | beliebig |
| ''BitsRotlPair'' | 128 Bit über ein Wortpaar |
> **''RotateLeft32'' aus ''std.conv'' war fehlerhaft** ([[https://github.com/SEOLizer/LyX-Compiler/issues/1546|#1546]]) und ist es **nicht mehr**. Gegen 1.0.21A geprüft: ''RotateLeft32'' und ''BitsRotl32'' liefern für ''0x12345678'' bei allen Weiten dieselben Werte, beide stimmen mit der Referenzrechnung überein. Dasselbe gilt für ''PopCount'' ([[https://github.com/SEOLizer/LyX-Compiler/issues/1545|#1545]]). Der Grund, hierher zu wechseln, ist also nicht mehr ein Defekt, sondern der größere Umfang — ''BitsRotlN'' und die Bitmengen unten.
----
===== Bitmengen =====
Eine Bitmenge ist ein Speicherblock, den der Aufrufer stellt. ''BitsetWords(n)'' sagt, wie viele 64-Bit-Wörter für ''n'' Bits nötig sind:
unit main;
import std.io;
import std.string;
import std.alloc;
import std.bits;
fn Z(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn main(): int64 {
var n: int64 := 200;
var bs: int64 := alloc(BitsetWords(n) * 8);
BitsetClearAll(bs, n);
BitsetSet(bs, 5);
BitsetSet(bs, 64);
BitsetSet(bs, 199);
Z("Count = ", BitsetCount(bs, n));
Z("Rank(100) = ", BitsetRank(bs, n, 100));
Z("Select(1) = ", BitsetSelect(bs, n, 1));
Z("Next(6) = ", BitsetNext(bs, n, 6));
return 0;
}
Count = 3
Rank(100) = 2
Select(1) = 64
Next(6) = 64
**Rank und Select sind das Paar, auf das es ankommt.** ''BitsetRank(bs, n, i)'' zählt die gesetzten Bits **vor** Position ''i'' — bei 100 sind das die Bits 5 und 64, also 2. ''BitsetSelect(bs, n, k)'' geht den umgekehrten Weg und liefert die Position des ''k''-ten gesetzten Bits, nullbasiert: ''Select(1)'' ist das zweite, also 64. ''BitsetNext(bs, n, from)'' findet das nächste gesetzte Bit ab einer Position — damit lässt sich eine dünn besetzte Menge durchlaufen, ohne alle 200 Positionen anzufassen.
^ Gruppe ^ Funktionen ^
| Anlegen | ''BitsetWords'' · ''BitsetClearAll'' · ''BitsetSetAll'' |
| Einzelbit | ''BitsetTest'' · ''BitsetSet'' · ''BitsetClear'' · ''BitsetToggle'' |
| Abfragen | ''BitsetCount'' · ''BitsetIsEmpty'' · ''BitsetRank'' · ''BitsetSelect'' · ''BitsetNext'' |
| Mengenverknüpfung | ''BitsetAnd'' · ''BitsetOr'' · ''BitsetXor'' · ''BitsetAndNot'' · ''BitsetNot'' |
| Vergleich | ''BitsetEquals'' · ''BitsetSubset'' |
| Zählen ohne Zwischenergebnis | ''BitsetCountAnd'' · ''BitsetCountOr'' · ''BitsetHamming'' |
| Verschieben | ''BitsetShl'' · ''BitsetShr'' · ''BitsetRotl'' · ''BitsetRotr'' |
''BitsetCountAnd(a, b, n)'' zählt die Bits im Schnitt, **ohne** den Schnitt zu bilden — für Ähnlichkeitsmaße über große Mengen der übliche Weg, weil kein Zielpuffer gebraucht wird.
> **Die Größe ''n'' wird nicht mitgeführt.** Jede ''Bitset*''-Funktion bekommt sie als Argument, und keine prüft sie gegen den tatsächlich reservierten Speicher. Wer ''alloc(BitsetWords(n) * 8)'' rechnet und später mit einem größeren ''n'' zugreift, schreibt in fremden Speicher. Die Größe gehört neben die Menge — als Konstante oder als Feld in der eigenen Struktur.
----
Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; Schiebe-, Zähl- und Rotationswerte gegen eine unabhängige Referenzrechnung geprüft.