Integer mit spezifischem Bitset generieren

Rikudo · 28. Juni 2015, 17:09

Moin,
Also, da der Titel vllt etwas unklar ist, versuche ich mein Vorhaben hier mal etwas genauer zu erklären

Ich möchte eine Funktion coden, welche einen byte als input Parameter schluckt.
Nennen wir diesen Parameter n.
Entsprechend des Input parameters n, welcher Maximal 32 betragen kann, und minimal 0 sein darf, soll eine Zahl im Bereich 0 - UInt32.Maxvalue zufällig ausgewählt werden
welche n bits gesetzt hat.
Beispiel:

Wäre als input parameter n die Zahl 6 gewählt worden, wäre 1337 ein möglicher Output, da dieser eben 6 Einsen bzw 6 gesetzte bits enthält.
Genauso könnte auch als Output z.B. die Zahl 2230 returned werden da diese ebenfalls 6 bits enthält:

Also kurz erklärt, ich möchte eine zufällig Zahl zwischen 0 und UInt32.MaxValue finden welche n gesetzte bits (angegeben durch den Input parameter) enhält.
Wie mach ich das am sinnvollsten?

Niko Ortner · 28. Juni 2015, 20:07

Ich hab mal was zusammengebastelt. Ist zwar VB, aber das Konvertieren sollte kein Problem sein.

VB.NET-Quellcode

Dim Rnd As New Random
Private Function GetRanomUInt32(HighBitCount As Integer) As UInt32
'Ungültige Werte abfangen
If HighBitCount < 0 OrElse HighBitCount > 32 Then
Throw New ArgumentOutOfRangeException("HighBitCount")
End If
'Corner Cases abfangen
If HighBitCount = 0 Then
Return 0
End If
If HighBitCount = 32 Then
Return UInt32.MaxValue
End If
Dim AvailableIndices = Enumerable.Range(0, 32).ToList 'Alle möglichen Indices von 0 bis 32 - 1
Dim Result As UInt32 = 0
For i = 1 To HighBitCount
Dim Index = AvailableIndices(Rnd.Next(0, AvailableIndices.Count)) 'Zufällig einen möglichen Index auswählen
Result = Result Or (1UI << Index) 'Das Bit an dem Index auf 1 setzen.
AvailableIndices.Remove(Index) 'Und den Index anschließend entfernen, sodass er nicht mehr verwendet werden kann.
Next
Return Result
End Function

Funktionieren tut das so: In AvailableIndices ist eine Liste aller möglichen Indices der Bits (also eine Liste von 0 bis 31). Bei jedem Durchlauf wird ein zufälliger Index ausgewählt. Das Bit an dem Index wird auf 1 gesetzt und der Index wird aus der Liste entfernt. Dadurch kann ein Index nie zweimal ausgewählt werden.
Eine mögliche Optimierung wäre das:

VB.NET-Quellcode

Dim IndexIndex = Rnd.Next(0, AvailableIndices.Count) 'Zufällig einen möglichen Index auswählen
Dim Index = AvailableIndices(IndexIndex)
Result = Result Or (1UI << Index) 'Das Bit an dem Index auf True setzen.
AvailableIndices.RemoveAt(IndexIndex) 'Und den Index anschließend entfernen, sodass er nicht mehr verwendet werden kann.

Dadurch muss nicht erst nach dem Index in der Liste gesucht werden, weil man weiß ja schon, wo der sein muss (IndexIndex).

ErfinderDesRades · 28. Juni 2015, 20:41

Das Durcheinanderwürfeln der Indizees kann man noch stark optimieren: Entweder mittm Fisher-Yates-Shuffle - Algo, oder mit Faktoriellen-Zerlegung einer einzelnen Zufallszahl

tolio · 28. Juni 2015, 20:41

C#-Quellcode

var rnd = new Random();
var count = 6;
var result = 0;
Enumerable.Range(0, count).ToList().ForEach((x) => { var i = 0; do { i = 1 << rnd.Next(0, 32); } while ((result & i) > 0); result |= i; });

Rikudo · 29. Juni 2015, 12:17

Niko Ortner schrieb:

Ich hab mal was zusammengebastelt. Ist zwar VB, aber das Konvertieren sollte kein Problem sein.

VB.NET-Quellcode

Dim Rnd As New Random

Private Function GetRanomUInt32(HighBitCount As Integer) As UInt32

'Ungültige Werte abfangen

If HighBitCount < 0 OrElse HighBitCount > 32 Then

Throw New ArgumentOutOfRangeException("HighBitCount")

End If

'Corner Cases abfangen

If HighBitCount = 0 Then

Return 0

End If

If HighBitCount = 32 Then

Return UInt32.MaxValue

End If

Dim AvailableIndices = Enumerable.Range(0, 32).ToList 'Alle möglichen Indices von 0 bis 32 - 1

Dim Result As UInt32 = 0

For i = 1 To HighBitCount

Dim Index = AvailableIndices(Rnd.Next(0, AvailableIndices.Count)) 'Zufällig einen möglichen Index auswählen

Result = Result Or (1UI << Index) 'Das Bit an dem Index auf 1 setzen.

AvailableIndices.Remove(Index) 'Und den Index anschließend entfernen, sodass er nicht mehr verwendet werden kann.

Next

Return Result

End Function

Funktionieren tut das so: In AvailableIndices ist eine Liste aller möglichen Indices der Bits (also eine Liste von 0 bis 31). Bei jedem Durchlauf wird ein zufälliger Index ausgewählt. Das Bit an dem Index wird auf 1 gesetzt und der Index wird aus der Liste entfernt. Dadurch kann ein Index nie zweimal ausgewählt werden.
Eine mögliche Optimierung wäre das:

VB.NET-Quellcode

Dim IndexIndex = Rnd.Next(0, AvailableIndices.Count) 'Zufällig einen möglichen Index auswählen

Dim Index = AvailableIndices(IndexIndex)

Result = Result Or (1UI << Index) 'Das Bit an dem Index auf True setzen.

AvailableIndices.RemoveAt(IndexIndex) 'Und den Index anschließend entfernen, sodass er nicht mehr verwendet werden kann.

Dadurch muss nicht erst nach dem Index in der Liste gesucht werden, weil man weiß ja schon, wo der sein muss (IndexIndex).

Da können aber auch negative Zählen auftreten,oder?

~blaze~ · 29. Juni 2015, 13:04

Hi
das geht noch wesentlich eleganter:
Nimm für ein Integer, das n zufällig gesetzte Bits haben soll, ein Integer, das bereits n gesetzte Bits hat (ohne Zufall) und vertausche einfach 32 mal je zwei zufällig gewählte Bits miteinander.
Bzw. ggf. reichen auch 16 Durchläufe.

Viele Grüße
~blaze~

ErfinderDesRades · 29. Juni 2015, 13:12

jo - geht in meine Richtung. Nur soll Herum-Vertauschen garnet so trivial sein, und allzuleicht verfällt man auf Algos, die dann doch wieder Häufungen produzieren.
Daher meine Empfehlung: zum "Mischen" den Fisher-Yates.

Niko Ortner · 29. Juni 2015, 16:24

negative Zählen

Huch? Wie das?
UInt32 ist ein Unsigned Integer mit 32 Bits. Das VB-Alias wäre UInteger. Das C#-Alias uint.

Rikudo · 29. Juni 2015, 17:26

~blaze~ schrieb:

Hi
das geht noch wesentlich eleganter:
Nimm für ein Integer, das n zufällig gesetzte Bits haben soll, ein Integer, das bereits n gesetzte Bits hat (ohne Zufall) und vertausche einfach 32 mal je zwei zufällig gewählte Bits miteinander.
Bzw. ggf. reichen auch 16 Durchläufe.

Viele Grüße
~blaze~

Heißt das ich brauch 31 "Beispiel-Ints" welche mir als Referenz dienen?
Und was meinst du mit 16 Durchläufen, kannst du das bitte nochmal genauer erläutern?:)

ErfinderDesRades · 29. Juni 2015, 17:39

also mein Vorschlag wäre:

mach dir ein Array mit 32 Booleans
setze 6 davon auf True, den Rest anders
MIsche das Array gut durch
durchlaufe das Array, und bei True setze entsprechend das Bit eines Integer - ungefähr wie von Niko gezeigt.

Rikudo · 29. Juni 2015, 18:04

tolio schrieb:

C#-Quellcode

var rnd = new Random();

var count = 6;

var result = 0;

Enumerable.Range(0, count).ToList().ForEach((x) => { var i = 0; do { i = 1 << rnd.Next(0, 32); } while ((result & i) > 0); result |= i; });

Deine Lösung funktioniert auch sehr gut, allerdings benötigt das ganze Linq (FW 3.0+).Wie schreib ich das am besten um so dasses auch für FW 2.0 funzt? ;D

ErfinderDesRades schrieb:

also mein Vorschlag wäre:
mach dir ein Array mit 32 Booleans
setze 6 davon auf True, den Rest anders
MIsche das Array gut durch
durchlaufe das Array, und bei True setze entsprechend das Bit eines Integer - ungefähr wie von Niko gezeigt.

1) Done.
2) Done.
3) Done.
4) Wie mach ich das jetzt, ich verstehs nich ganz.

C#-Quellcode

private static UInt32 GenerateSpecificBitInteger(int bits)
{
bool[] arr = new bool[32];
for (int i = 0; i < 6; i++)
arr[i] = true;
int n = arr.Length;
for (int i = 0; i < n; i++)
{
int r = i + (int)(Rnd.NextDouble() * (n - i));
bool t = arr[r];
arr[r] = arr[i];
arr[i] = t;
}
for (int i = 0; i < n; i++)
{
// Hm, ... wie die Bits setzen
}
}

ErfinderDesRades · 29. Juni 2015, 18:11

wie man ein bit an einem Index setzt, hat Niko doch gezeigt - ist daran iwas unklar?

VB.NET-Quellcode

Result = Result Or (1UI << Index)

tipp: dein i ist der Index, und mit einem if(arr(i)) prüfst du, ob das bit zu setzen ist.

(Übrigens mir was, als hätte ich dir schonmal empfohlen, als kleine Erleichterung für so Sachen eine .Swap-Extension einzuführen.)

Niko Ortner · 29. Juni 2015, 18:18

Das Array würfeln geht übrigens einfacher... bzw. weiß ich nicht, ob das mitm .Net Framework 2.0 auch geht.

VB.NET-Quellcode

Dim Rnd As New Random
Function F(HighBitCount As Integer) As UInt32
'Ungültige Werte abfangen
If HighBitCount < 0 OrElse HighBitCount > 32 Then
Throw New ArgumentOutOfRangeException("HighBitCount")
End If
'Corner Cases abfangen
If HighBitCount = 0 Then
Return 0
End If
If HighBitCount = 32 Then
Return UInt32.MaxValue
End If
'Array erstellen
Dim Bits = New Boolean(32 - 1) {}
For i = 0 To HighBitCount - 1
Bits(i) = True
Next
'Array durcheinanderwürfeln
Array.Sort(Bits, Function(Left, Right) If(Rnd.NextDouble < 0.5, -1, 1))
'Integer zusammenbasteln
Dim Result As UInt32 = 0
For i = 0 To 31
If Bits(i) Then
Result = Result Or (1UI << i)
End If
Next
Return Result
End Function

PS:

Huch? Wie das?

ErfinderDesRades · 29. Juni 2015, 18:25

ja, aber Fisher-Yates ist vielfach performanter, ich nehme an, Rikudo will da was schnelles haben.

edit:
also glaub ich zumindest, aber wenn die Random-Funktion das überaus langsamte Element ist, dann wärs wohl egal, wenn man das eigliche Mischen der vergleichsweise aufwändigen Sort-Methode mit ihren Mehrfach-Durchgängen überantwortet.

Rikudo · 29. Juni 2015, 18:42

Habs so gemacht (Danke an tolio) :

C#-Quellcode

private static uint GenerateSpecificBitInteger(uint n)
{
uint res = 0;
for (int x = 0; x < n; x++)
{
uint i = Convert.ToUInt32((uint)1 << rnd.Next(0, 32));
while ((res & i) > 0)
i = Convert.ToUInt32((uint)1 << rnd.Next(0, 32));
res = res | i;
}
return res;
}

~blaze~ · 29. Juni 2015, 19:04

Hi
ggf. so?

VB.NET-Quellcode

Shared Function GenerateUInt32(n As Integer) As UInteger
If n = 0 Then Return 0
If n < 0 OrElse n > 32 Then Throw New ArgumentOutOfRangeException("n")
Dim rnd As New Random()
Dim result As UInteger = &HFFFFFFFFUI >> (32 - n) 'n Bits bleiben über
For i As Integer = 1 To 32
Dim j As Integer = rnd.Next(0, 32)
'(result And Not ((1UI << i) Or (1UI << j))) entfernt je die beiden Werte, die vertauscht werden sollen
'(((result >> x) And 1UI) << y) entspricht x nach y schieben
result = (result And Not ((1UI << i) Or (1UI << j))) Or (((result >> i) And 1UI) << j) Or (((result >> j) And 1UI) << j)
Next
Return result
End Function

Ist wieder mal nicht getestet, da es sonst dem Faulheitsprinzip widerspricht, aber könnte mir vorstellen, dass es funktioniert.

Viele Grüße
~blaze~

Rikudo · 29. Juni 2015, 19:30

*Vollzitat entfernt*

Hey,
Danke für deinen Ansatz.
Mein versuch den nach C# umzuschreiben mit Converter + Hand:

C#-Quellcode

public static uint GenerateUInt32(int n)
{
if (n == 0)
return 0;
if (n < 0 || n > 32)
throw new ArgumentOutOfRangeException("n");
Random rnd = new Random();
uint result = 0xffffffffu >> (32 - n);
for (int i = 1; i <= 32; i++)
{
int j = rnd.Next(0, 32);
result = (result & !((1u << i) | (1u << j))) | (((result >> i) & 1u) << j) | (((result >> j) & 1u) << j);
}
return result;
}

Operator '!' cannot be applied to operand of type 'uint'.

C#-Quellcode

result = (result & !((1u << i) | (1u << j))) | (((result >> i) & 1u) << j) | (((result >> j) & 1u) << j);

Irgendwie sind die Klammern hier falsch, ich kriegs aber nicht gebacken sie richtig zu setzen, bzw den entsprechende typcast [?] durchzuführen?

Edit by ~blaze~:
*Vollzitat entfernt*

tolio · 29. Juni 2015, 19:40

C#-Quellcode

var rnd = new Random();
var count = 6;
var result = 0;
while (count > 0)
{
var y = 1 << rnd.Next(0, 32);
if (!((result & y) > 0))
{
result |= y;
count--;
}
}

~blaze~ · 29. Juni 2015, 19:46

~ ist das zugehörige Äquivalent in C#. ! ist's nur bei Boolean.
Konvertierung von uint-Daten in int-Daten geht btw. einfach über unchecked((int)uintvalue)

Der Algorithmus von tolio terminiert leider nicht zwangsweise und ist u.U. ineffizient, sonst wäre es ggf. schon praktisch, das so zu lösen (hatte ich aber aus genannten Gründen verworfen)

Viele Grüße
~blaze~

Rikudo · 29. Juni 2015, 19:50

tolio schrieb:

C#-Quellcode

var rnd = new Random();

var count = 6;

var result = 0;

while (count > 0)

{

var y = 1 << rnd.Next(0, 32);

if (!((result & y) > 0))

{

result |= y;

count--;

}

}

Danke das funktioniert ebenfalls

~blaze~ schrieb:

~ ist das zugehörige Äquivalent in C#. ! ist's nur bei Boolean.
Konvertierung von uint-Daten in int-Daten geht btw. einfach über unchecked((int)uintvalue)

Der Algorithmus von tolio terminiert leider nicht zwangsweise und ist u.U. ineffizient, sonst wäre es ggf. schon praktisch, das so zu lösen (hatte ich aber aus genannten Gründen verworfen)

Viele Grüße
~blaze~

Dann funktioniert deine Funktion aber nicht ganz richtig

(oder ich habs falsch umgeschrieben? ;o )

C#-Quellcode

public static uint GenerateUInt32(int n)
{
if (n == 0)
return 0;
if (n < 0 || n > 32)
throw new ArgumentOutOfRangeException("n");
uint result = 0xffffffffu >> (32 - n);
for (int i = 1; i < 32; i++)
{
int j = rnd.Next(0, 32);
result = (result & ~((1u << i) | (1u << j))) | (((result >> i) & 1u) << j) | (((result >> j) & 1u) << j);
}
return result;
}

Jedenfalls haben die Outputs uints nicht immer n bits, sondern oftmals auch n-1, n-2 oder n-3

Integer mit spezifischem Bitset generieren

Integer mit spezifischem Bitset generieren

VB.NET-Quellcode

VB.NET-Quellcode

C#-Quellcode

Niko Ortner schrieb:

VB.NET-Quellcode

VB.NET-Quellcode

~blaze~ schrieb:

tolio schrieb:

C#-Quellcode

ErfinderDesRades schrieb:

C#-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

C#-Quellcode

VB.NET-Quellcode

C#-Quellcode

C#-Quellcode

C#-Quellcode

tolio schrieb:

C#-Quellcode

~blaze~ schrieb:

C#-Quellcode

Ähnliche Themen

5 Benutzer haben hier geschrieben