PRNG zur exakten Generierung von Zahlen mit n gesetzten Bits

Ich schreibe gerade Code, um Binärdaten zu generieren. Ich muss speziell 64-Bit-Zahlen mit einer bestimmten Anzahl von gesetzten Bits generieren. Genauer gesagt sollte die Prozedur einige annehmen und eine pseudozufällige 64-Bit-Zahl mit genau auf gesetzten Bits und den Rest auf 0 setzen.$0 < n < 64$$n$$1$

Mein aktueller Ansatz sieht ungefähr so ​​aus:

1. Erzeugen Sie eine pseudozufällige 64-Bit-Zahl .$k$
2. Zähle die Bits in und speichere das Ergebnis in .$k$$b$
3. Wenn , wird ausgegeben ; ansonsten gehe zu 1.$b = n$$k$

Das funktioniert, aber es scheint unelegant. Gibt es eine Art PRNG-Algorithmus, der Zahlen mit gesetzten Bits eleganter erzeugen kann als dies?$n$

Was Sie brauchen, ist eine Zufallszahl zwischen 0 und . Das Problem ist dann, dies in das Bitmuster umzuwandeln.${ 64 \choose n } - 1$

Dies wird als Aufzählungscodierung bezeichnet und ist einer der ältesten verwendeten Komprimierungsalgorithmen. Der wahrscheinlich einfachste Algorithmus stammt von Thomas Cover. Es basiert auf der einfachen Beobachtung, dass, wenn Sie ein Wort haben, das Bits lang ist, wobei die gesetzten Bits x k … x 1 in der höchstwertigen Bitreihenfolge sind, die Position dieses Wortes in der lexikografischen Reihenfolge aller Wörter mit diesem Eigentum ist:$n$$x_k \ldots x_1$

So zum Beispiel für ein 7-Bit-Wort:

i(0001011)= (

...und so weiter.

Um das Bitmuster von der Ordnungszahl zu erhalten, dekodieren Sie einfach jedes Bit der Reihe nach. So etwas in einer C-ähnlichen Sprache:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Da Sie nur Binomialkoeffizienten bis zu 64 benötigen, können Sie diese vorberechnen.

• Cover, T., Enumerative Source Encoding . IEEE Transactions on Information Theory, Band IT-19, Nr. 1, Januar 1973.

Sehr ähnlich der Antwort von Pseudonym, die mit anderen Mitteln erhalten wurde.

Die Gesamtzahl der verfügbaren Kombinationen kann mit der Sternen - und Balken - Methode ermittelt werden , daher muss . Die Gesamtzahl der 64-Bit-Nummern, von denen Sie versuchen würden, Ihre Nummer abzutasten, wäre offensichtlich viel höher.$c=\binom{64}{n}$

Was Sie dann brauchen, ist eine Funktion, die Sie von einer Pseudozufallszahl im Bereich von 1 bis c zur entsprechenden 64-Bit-Kombination führen kann.$k$$1$$c$

Pascals Dreieck kann Ihnen dabei helfen, da der Wert jedes Knotens genau die Anzahl der Pfade von diesem Knoten zur Wurzel des Dreiecks darstellt und jeder Pfad eine der Zeichenfolgen darstellen kann, nach denen Sie suchen, wenn alle Linksabbiegungen vorhanden sind Beschriftet mit einer und bei jeder Rechtskurve mit einer 0 .$1$$0$

Also sei die Anzahl der noch zu bestimmenden Bits und y die Anzahl der noch zu verwendenden Bits .$x$$y$

Wir wissen, dass , und wir können es verwenden, um das nächste Bit der Zahl bei jedem Schritt richtig zu bestimmen:$\binom{x}{y}=\binom{x-1}{y}+\binom{x-1}{y-1}$

$\mathtt{while}\;\;\; x>0$

$\quad \mathtt{if}\;\;\; x>y$

$\qquad \mathtt{if}\;\;\;k>\binom{x-1}{y}: \;\;\;s \leftarrow s\; + \mathtt{"1"}, \;k\leftarrow k-\binom{x-1}{y}, \;y \leftarrow y-1$

$\qquad \mathtt{else}:\; \;s \leftarrow s\; + \mathtt{"0"}$

$\quad \mathtt{else}: \;\;s \leftarrow s\; + \mathtt{"1"}, \;y \leftarrow y-1$

$\quad x \leftarrow x-1$

Eine andere sehr elegante Methode ist die Verwendung der in dieser Stapelüberlaufantwort beschriebenen Halbierung . Die Idee ist, zwei Wörter zu behalten, von denen bekannt ist, dass sie höchstens k Bits haben und von denen bekannt ist, dass sie mindestens k Bits haben, und Zufälligkeit zu verwenden, um eines von diesen zu bewegen, um genau k Bits zu haben. Hier ist ein Quellcode zur Veranschaulichung:

word randomKBits(int k) {
    word min = 0;
    word max = word(~word(0)); // all 1s
    int n = 0;
    while (n != k) {
        word x = randomWord();
        x = min | (x & max);
        n = popcount(x);
        if (n > k)
            max = x;
        else
            min = x;
    }
    return min;
}

Ich habe einen Leistungsvergleich verschiedener Methoden durchgeführt. Diese Methode ist normalerweise die schnellste, es sei denn, k ist als sehr klein bekannt.

Sie können Folgendes tun:

$k$$1$$64$

$k$$0$$1$

$n$

$A[]$$64$$0$

for(i=1 to n)
{
    k=ran(1,65-i) % random number between 1 and 65-i
    for(x=1;x<65;x++)
    {
        if(A[x]==0)k--;
        if(k==0)break;
    }
    A[x]=1;
}