std.bits — Bitoperationen

Schieben und Rotieren mit vorhersagbarem Verhalten, Zählfunktionen über alle 64 Bit und Bitmengen beliebiger Größe mit Rank und Select.

→ Mathematik-Units · std.i128 · std.math · 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.

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.

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.

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

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:

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.

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.

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.