Random byte mit set bits?

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von 3daycliff.

    Random byte mit set bits?

    Heyyo Community,

    Also ein byte besteht ja immer aus 8 bits.
    Gibt es eine Mglichkeit ein random-byte zu generieren mit folgender Bedingung:
    • Das byte muss mindestens 2 gestzte bits haben
    • Das byte darf maximal 7 gesetzte bits haben.
    Wie stelle ich das am besten an?
    Mir ist bekannt das ich mit Random.NextByte() ein random-byte generieren kann, aber nicht wie ich ein byte
    generiere das die Bedingung erfüllt.
    C# Developer
    Learning C++

    Hi
    die erste Bedingung ist recht einfach:
    Nimm eine Zufallszahl und setze zwei voneinander verschiedene Bits:

    C#-Quellcode

    1. int offs1 = random.Next(0, 8);
    2. int offs2 = (random.Next(0, 7) + offs1) % 8;
    3. int b = random.Next(0, 256) | (1 << offs1) | (1 << offs2);

    für die zweite fällt mir tatsächlich nur eine Hässlichkeit ein, damit alles fair ist:

    C#-Quellcode

    1. if (b == 0xff)
    2. b ^= (1 << (random.Next(0, 8));

    b sollte dann eine Zahl zwischen 0 und 255 enthalten.

    Das "solange bis" bei Zufallszahlen ist ziemlich schlecht. Auch wenn die Wahrscheinlichkeit mit zunehmender Zahl des "Würfelns" immer geringer wird, dass keine solche Zahl gefunden wird, ist sie nicht zu vernachlässigen. Die worst case Laufzeit für deinen Algorithmus ist "unendlich".

    Viele Grüße
    ~blaze~

    Bluespide schrieb:

    Du könntest die Bits zählen und so lange ein neues Generieren bis es passt: What is the fastest way to count set bits in UInt32 in C#

    Ist mir bekannt, dafür geht der HammingWeight algo, allerdings ist dein vorgehen ein bisschen unschön, ist quasi eine Art "brutforcen" bis es passt :D

    ~blaze~ schrieb:

    Hi
    die erste Bedingung ist recht einfach:
    Nimm eine Zufallszahl und setze zwei voneinander verschiedene Bits:

    C#-Quellcode

    1. int offs1 = random.Next(0, 8);
    2. int offs2 = (random.Next(0, 7) + offs1) % 8;
    3. int b = random.Next(0, 256) | (1 << offs1) | (1 << offs2);

    für die zweite fällt mir tatsächlich nur eine Hässlichkeit ein, damit alles fair ist:

    C#-Quellcode

    1. if (b == 0xff)
    2. b ^= (1 << (random.Next(0, 8));

    b sollte dann eine Zahl zwischen 0 und 255 enthalten.

    Das "solange bis" bei Zufallszahlen ist ziemlich schlecht. Auch wenn die Wahrscheinlichkeit mit zunehmender Zahl des "Würfelns" immer geringer wird, dass keine solche Zahl gefunden wird, ist sie nicht zu vernachlässigen. Die worst case Laufzeit für deinen Algorithmus ist "unendlich".

    Viele Grüße
    ~blaze~

    Sieht auf jeden Fall interessant aus, werde ich gleich mal versuchen!
    C# Developer
    Learning C++

    Hoppla, es muss natürlich

    C#-Quellcode

    1. int offs2 = (random.Next(0, 7) +1 + offs1) % 8;

    lauten, danke für den Hinweis. ;)

    btw: Erkennen ist das eine, aber beheben ist das andere @Rikudo. Der Sinn von offs1 und offs2 ist, ein Bit je ein Bit zu setzen, wobei kein Bit doppelt vorkommen soll. D.h. für das erste Bit stehen die vollen 8 Bit zur Verfügung. Für das zweite Bit stehen nur noch 7 Bit zur Verfügung, wobei man die Dopplung vermeidet, indem man vom vorherigen Bit eine zufällige Zahl an Stellen nach links geht und nach dem 8. Bit wieder rechts beim 1. Bit beginnt.
    Ich glaube nicht, dass mein Algorithmus fair ist. 7 gesetzte Bits müssten häufiger auftreten, als die anderen.

    Viele Grüße
    ~blaze~

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „~blaze~“ ()

    Eine etwas andere Herangehensweise:
    Es gibt nur sehr wenige, mögliche Werte. Weniger als 256. Man könnte diese Werte einfach vorausberechnen und in einer Liste speichern.

    C#-Quellcode

    1. private static List<byte> PossibleResults = (from b in Enumerable.Range(0, 256)
    2. let bits = NumberOfSetBits(b) // Wie auch immer das berechnet wird.
    3. where 2 <= bits && bits <= 7
    4. select (byte)b).ToList();
    5. private static Random Rnd = new Random();
    6. public static byte GetRandomValue()
    7. {
    8. return PossibleResults[Rnd.Next(0, PossibleResults.Count)];
    9. }
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Niko Ortner schrieb:

    Eine etwas andere Herangehensweise:
    Es gibt nur sehr wenige, mögliche Werte. Weniger als 256. Man könnte diese Werte einfach vorausberechnen und in einer Liste speichern.

    C#-Quellcode

    1. private static List<byte> PossibleResults = (from b in Enumerable.Range(0, 256)
    2. let bits = NumberOfSetBits(b) // Wie auch immer das berechnet wird.
    3. where 2 <= bits && bits <= 7
    4. select (byte)b).ToList();
    5. private static Random Rnd = new Random();
    6. public static byte GetRandomValue()
    7. {
    8. return PossibleResults[Rnd.Next(0, PossibleResults.Count)];
    9. }


    Danke für deine Antwort.
    Das berechnen der gesetzten Bits geht mit dem HammingWeight algo, also so:

    C#-Quellcode

    1. /// <summary>
    2. /// Count the set bits in a ulong using 24 arithmetic operations (shift, add, and)..
    3. /// </summary>
    4. /// <param name="x">The ulong of which we like to count the set bits.</param>
    5. /// <returns>Amount of set bits.</returns>
    6. private static int HammingWeight(ulong x)
    7. {
    8. x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); //put count of each 2 bits into those 2 bits
    9. x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); //put count of each 4 bits into those 4 bits
    10. x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f); //put count of each 8 bits into those 8 bits
    11. x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff); //put count of each 16 bits into those 16 bits
    12. x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff); //put count of each 32 bits into those 32 bits
    13. x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff); //put count of each 64 bits into those 64 bits
    14. return (int)x;
    15. }


    (Für byte oder int oder short etc einfahc die pattern verkürzen)
    C# Developer
    Learning C++

    Mir ist noch eine einfache, faire Version eingefallen:
    - Berechne 8 Zufallszahlen mit jeweils 5 Bit (d.h. 2 Int-Zufallszahlen von denen 40 Bit genutzt werden)
    - Ordne die Bitfolge 0xff >> (1 + rnd(6)) zufällig an. die [color=#ff00]1[/color] ergibt sich, da höchstens 7 Bit gesetzt sind, ergo 1 Bit ungesetzt ist, die 6 ergibt sich, da mindestens zwei Bits gesetzt sein müssen, ergo maximal 6-[color=#ff00]1[/color] Bits nach rechts shiften. Die Anordnung geschieht mit den Zufallszahlen aus Schritt 1.

    C#-Quellcode

    1. long rndnrs = ((long)rnd.Next() << 32) | rnd.Next();
    2. int v = (byte)0xff;
    3. for(int i = 0; i < 8; i++) //durchlaufe alle Bitstellen
    4. {
    5. int rn = (rndnrs >> (i * 5)) & 0x1f; //bestimme die 5 Bit lange Zufallszahl für die i-te Bitstelle
    6. //Vertausche Bit i mit Bit rn
    7. //Schritt 1: Entferne die Bits i und rn: (v & ~((1 << rn) | (1 << i)))
    8. //Schritt 2: Verschiebe Bit rn an die i-te Stelle und füge es ins Resultat ein: ((1 << i) * ((v >> rn) & 1))
    9. //Schritt 3: Verschiebe Bit i an die rn-te Stelle und füge es ins Resultat ein: ((1 << rn) * ((v >> i) & 1))
    10. v = (v & ~((1 << rn) | (1 << i))) | ((1 << i) * ((v >> rn) & 1)) | ((1 << rn) * ((v >> i) & 1))
    11. }

    Schritt 2 und Schritt 3 sind symmetrisch bzgl. i und rn. Ich hoff', ich hab' jetzt keinen Denkfehler bei den Bitoperationen am Schluss... Der Sinn ist, erst das i-te bzw. rn-te Bit zu setzen und es dann auf 0 oder 1 zu setzen, was durch eine Multiplikation mit dem Quellwert geschehen soll, da (v >> x) & 1 den Wert des i-ten Bits ausgibt.

    Viele Grüße
    ~blaze~

    Aufpassen, du musst noch die anderen Bits setzen. Problematisch bei der Zufallszahlengenerierung ist, dass man keine Zahl bevorzugen darf. Alle Ergebnisse "müssen" gleich wahrscheinlich sein (außer eine andere Verteilung ist gewünscht, z.B. Normalverteilung), sonst kommt es ggf. zu ausnutzbaren Fehlern, etc. Deswegen tat ich mich am Anfang auch so schwer mit dem Algorithmus. Lustigerweise hatte ich ganz am Anfang die Idee mit dem Vertauschen schon, aber aus irgendeinem Grund hab' ich die wieder verworfen...

    OT:
    Wir hatten auch mal das Problem, eine Zufallszahl zu erzeugen, die zwischen a und b (ergo a+rnd(0, b-a)) liegt und nur Zufallszahlen zwischen 0 und 255 zur Verfügung stehen. Selbiges Problem, schon allein mir fallen 6 Arten ein, sowas zu lösen, die "unfair" sind 1 guter und ein paar Ansätze, aber die Qualität ist dann halt einfach schlecht.
    Es ist halt an sich überhaupt noch total das triviale Problem, aber man muss sich reindenken. :rolleyes:

    Viele Grüße
    ~blaze~

    ~blaze~ schrieb:

    Wir hatten auch mal das Problem, eine Zufallszahl zu erzeugen, die zwischen a und b (ergo a+rnd(0, b-a)) liegt und nur Zufallszahlen zwischen 0 und 255 zur Verfügung stehen.

    Hey, das war ich :D Zufallswert mit Maximum aus 8-Bit Zufallswert ohne Bias nur halt von 0 bis n.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Ja genau, ich hatte sogar überlegt, ob du das warst oder Rikudo selbst ;) a ist bei dir halt 0.
    Der Trick dabei wäre, das höchste gesetzte Bit in b-a zu ermitteln und solange Bit i (i wird in jedem Durchlauf dekrementiert) aus einem Zufallswert c mit Bit i aus b-a in einem Ergebnis zu verunden, bis das Bit in b-a 1 und das in c 0 ist. Die restlichen i bis 0 Bits in r werden dann auf die aus c gesetzt.

    Viele Grüße
    ~blaze~

Facebook
Telefonspende