[C#] Codieren von Informationen mittels bitwise-Operators

    • C#
    • .NET (FX) 4.5–4.8

    Es gibt 2 Antworten in diesem Thema. Der letzte Beitrag () ist von φConst.

      [C#] Codieren von Informationen mittels bitwise-Operators

      Hallo,

      vermutlich zu leicht für das Unter-Forum, kann aber als Einstieg dann doch nützlich sein.

      Ziel ist es:

      Lieblingsgetränk, Geschlecht und Haustier mittels bitwise-Operatoren ( | & ~ et cetera, siehe wiki), zu konkatenieren und sie so kompakt als Integer-Wert darzustellen.

      Kurze Einführung:

      Bitwise-Operatoren werden - wie der Name bereits suggeriert - auf Bits angewandt; daraus ergibt sich: Nur Ganzzahlen; Fließkommazahlen werden intern anders repräsentiert ( Basis, Mantisse, Exponent) weswegen auf diese
      keine solcher Operatoren ausgeführt werden können (es macht keinen Sinn, aufgrund eben ihrer internen Repräsentation).

      Jeder Integer-Wert (aber auch short und dergleichen), wird binär behandelt.
      Die Zahl 1 würde lauten:
      00000000000000000000000000000001
      Zahl 2:
      00000000000000000000000000000010
      Zahl 3:
      00000000000000000000000000000011

      et cetera

      Die Umrechnung vom Dezimal-System ins Binär-System erfolgt über eine rekursiv definierte Folge von Anwendung des DIV und MOD Operators, soll heißen: Die Zahl 5 im Binärsystem würde lauten:

      5 DIV 2 = 2 | 5 MOD 2 = 1
      2 DIV 2 = 1 | 2 MOD 2 = 0
      1 DIV 2 = 0 | 1 MOD 2 = 1


      DIV ist dabei der "geteilt durch" Operator, Mod ist der Rest, heißt: mod(a,b) = a - ( int(a/b) * b)

      Wobei int(x) die Nachkommstelle der Zahl x abschneidet.

      Die Leserichtung geht von unten nach oben, die Zahl 5 im Binärsystem ist demnach 101

      Die Umrechnung vom Binär -zum Dezimalsystem geht wesentlich schneller über das sogenannte Horner-Schema.

      Ganz schnell nur:

      Basis = 2| 1 0 1
      #######|##2#2
      _________________________
      #########1#2#5


      Zurück zum eigentlichen Thema:

      Die für dieses Tutorial notwendigen Operatoren sind das bitwise-ODER "|", das bitwise-AND "&" und left-Shift "<<".

      Gesetzt den Fall wir haben die Zahl

      C#-Quellcode

      1. int num = 5


      Dann ist seine binäre Repräsentation:
      0000101


      Ein shift nach links würde bedeuten, dass wir alle Bits eins nach links verschieben; dabei wird am Anfang, also rechts, eine Null drangehängt.

      Das sähe dann folgendergestalt aus:

      C#-Quellcode

      1. int numShifted = num << 1

      0001010


      Der & Operator wird auf zwei ganzzahlige Datentypen angewandt; dabei wird jedes bit mit dem jeweils anderen verglichen, es gelten die typischen boolesche Gesetzen, also

      1 UND 1 = 1
      1 UND 0 = 0
      0 UND 1 = 0
      0 UND 0 = 0

      Dies ist essenziell, um die encodierten Daten, am Ende zu dekodieren.
      Dafür erstellen wir einfach eine sogenannte Maske, dazu später _ mehr.


      Der |-Operator ist evident:

      1 ODER 0 = 1
      0 ODER 1 = 1
      1 ODER 1 = 1
      0 ODER 0 = 0

      Das ist notwendig, wenn wir mehrere "Eigenschaften" (Werte) verknüpfen wollen.

      Für das Encoding ist im Grunde lediglich der Shift-Operator notwendig.
      Dafür definieren wir für jede Eigenschaft eine maximale Anzahl an Bits.

      Exemplarisch werden wir gleich sehen, dass wir 7 Getränke zur Auswahl haben, 7 im Binärsystem ist 111; die maximale Anzahl beträgt also 3, dass offSet für die nächste
      Information ist also a(max_x_binary) kummuliert, wobei a, die Anzahl der Ziffern und max_x_binary die höchst festgelegte Zahl die die Information codieren soll, ist (in diesem Falle 7, also 111).

      Ich definiere sie als: a(x) = int(log10(x)+1)

      Was int() ist wurde oben kurz behandelt.
      Die Funktion gibt zu einer beliebigen Zahl, die Anzahl ihrer Ziffern zurück.

      Beispiel:

      Wir wollen die Informationen Lieblingsgetränk (7 stehen zur Auswahl), Geschlecht und Haustier codieren.

      Wir wandeln 7 ins Binär-System, und übergeben sie a(111) = 3

      Der offSet (also um wie viel Bits nach links geshifted werden soll) für das Geschlecht beträgt demnach 3.
      Das Geschlecht wird definiert als 1/0, wobei 1 für weiblich, 0 für männlich steht; der offSet für die nächste Information ist also a(111)+a(1) = 4.

      Nun wird Haustier (repräsentiert als Zahl zwischen 1 und 3, in binärer Schreibweise also maximal 11) 4 Bits nach links geshifted.

      Folgende Werte habe ich festgelegt:

      C#-Quellcode

      1. public const int MILK = 1; // 000000001
      2. public const int WATER = 2; // 000000010
      3. public const int RED_BULL = 3; // 000000011
      4. public const int APPLE_JUICE = 4; // 000000100
      5. public const int ORANGE_JUICE = 5; // 000000101
      6. public const int TAMARIND = 6; // 000000110
      7. public const int SPRITE = 7; // 000000111
      8. public const int MASCULINE = 0 << 3; // 00000X000
      9. public const int FEMININE = 1 << 3; // 000001000
      10. public const int CAT = 1 << 4; // 000010000
      11. public const int DOG = 2 << 4; // 000100000
      12. public const int BIRD = 3 << 4; // 000110000



      Wir erstellen eine Methode die als Parameter drei Integer-Werte annimmt, die jeweils eines der Konstanten erhalten:

      C#-Quellcode

      1. public static int Encode(int drink, int gender, int animal)
      2. {
      3. int mask = 00000000;
      4. mask = drink | gender | animal;
      5. return mask;
      6. }



      Die Variable "mask" ist nicht notwendig; dient aber zur Anschauung.

      Über "|" verknüpfen wir nun jedes dieser Informationen miteinander.
      Das geht weil exemplarisch die Information für "CAT" repräsentiert wird als 000010000 und für "SPRITE" 000000111; diese beiden verknüpft ergibt (siehe boolsche Algebra)

      000010000
      000000111
      ------------
      000010111


      Diese Information codiert: SPRITE - MÄNNLICH - KATZE


      Die Decodier-Methode:

      Spoiler anzeigen

      C#-Quellcode

      1. public static string[] Decode(int encoded)
      2. {
      3. string[] values = new string[3];
      4. int mask = 7; // 000000111
      5. int drink = encoded & mask;
      6. mask = 1 << 3; // 000001000
      7. int gender = mask & encoded;
      8. mask = 3 << 4; // 000110000
      9. int animal = mask & encoded;
      10. switch (drink)
      11. {
      12. case MILK:
      13. values[0] = "Milk";
      14. break;
      15. case WATER:
      16. values[0] = "Water";
      17. break;
      18. case RED_BULL:
      19. values[0] = "RedBull";
      20. break;
      21. case APPLE_JUICE:
      22. values[0] = "Apple juice";
      23. break;
      24. case ORANGE_JUICE:
      25. values[0] = "Orange juice";
      26. break;
      27. case TAMARIND:
      28. values[0] = "Tamarind";
      29. break;
      30. case SPRITE:
      31. values[0] = "Sprite";
      32. break;
      33. }
      34. values[1] = (gender == 0) ? "Masculine" : "Feminine";
      35. switch (animal)
      36. {
      37. case CAT:
      38. values[2] = "Cat";
      39. break;
      40. case DOG:
      41. values[2] = "Dog";
      42. break;
      43. case BIRD:
      44. values[2] = "Bird";
      45. break;
      46. }
      47. return values;
      48. }


      Ich weiß: Kann man sauberer programmieren (Enums); soll ja aber einen didaktischen Zweck erfüllen.


      Die oben kurz erwähnte Maske ist dafür notwendig, dass wir die jeweils spezifische Information filtern, exemplarisch:

      000010111 (obiges Beispiel)
      Wir wollen wissen, welches Getränk die Zahl codiert.

      Daher die Maske:
      000000111


      Wir haben ja nämlich oben festgelegt, dass Getränke die ersten drei Bits beanspruchen soll.
      Applizieren wir nun auf beide Werte den &-Operator, erhalten wir:

      000000111

      Nun wird über eine Switch-Case-Anweisung derjenige Fall selektiert, der denselben Wert hält; das ist offensichtlich Sprite.

      Hier das komplette Programm:
      Spoiler anzeigen

      C#-Quellcode

      1. namespace BitShifts
      2. {
      3. class Program
      4. {
      5. public const int MILK = 1; // 000000001
      6. public const int WATER = 2; // 000000010
      7. public const int RED_BULL = 3; // 000000011
      8. public const int APPLE_JUICE = 4; // 000000100
      9. public const int ORANGE_JUICE = 5; // 000000101
      10. public const int TAMARIND = 6; // 000000110
      11. public const int SPRITE = 7; // 000000111
      12. public const int MASCULINE = 0 << 3; // 00000X000
      13. public const int FEMININE = 1 << 3; // 000001000
      14. public const int CAT = 1 << 4; // 000010000
      15. public const int DOG = 2 << 4; // 000100000
      16. public const int BIRD = 3 << 4; // 000110000
      17. static void Main(string[] args)
      18. {
      19. int encoded = Encode(SPRITE, FEMININE, CAMEL);
      20. string[] vals = Decode(encoded);
      21. foreach (var item in vals)
      22. Console.WriteLine(item);
      23. Console.WriteLine(int.MaxValue);
      24. Console.Read();
      25. }
      26. public static int Encode(int drink, int gender, int animal)
      27. {
      28. int mask = 00000000;
      29. mask = drink | gender | animal;
      30. return mask;
      31. }
      32. public static string[] Decode(int encoded)
      33. {
      34. string[] values = new string[3];
      35. int mask = 7; // 000000111
      36. int drink = encoded & mask;
      37. mask = 1 << 3; // 000001000
      38. int gender = mask & encoded;
      39. mask = 3 << 4; // 000110000
      40. int animal = mask & encoded;
      41. switch (drink)
      42. {
      43. case MILK:
      44. values[0] = "Milk";
      45. break;
      46. case WATER:
      47. values[0] = "Water";
      48. break;
      49. case RED_BULL:
      50. values[0] = "RedBull";
      51. break;
      52. case APPLE_JUICE:
      53. values[0] = "Apple juice";
      54. break;
      55. case ORANGE_JUICE:
      56. values[0] = "Orange juice";
      57. break;
      58. case TAMARIND:
      59. values[0] = "Tamarind";
      60. break;
      61. case SPRITE:
      62. values[0] = "Sprite";
      63. break;
      64. }
      65. values[1] = (gender == 0) ? "Masculine" : "Feminine";
      66. switch (animal)
      67. {
      68. case CAT:
      69. values[2] = "Cat";
      70. break;
      71. case DOG:
      72. values[2] = "Dog";
      73. break;
      74. case BIRD:
      75. values[2] = "Bird";
      76. break;
      77. }
      78. return values;
      79. }
      80. }
      81. }



      Viel Spaß.

      Besonders lange Programmausschnitte kann man super in Spoiler-Tags "verstecken" ;) Editiert. ~fufu
      Und Gott alleine weiß alles am allerbesten und besser.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „fufu“ ()

      @φConst Warum nimmst Du kein Flags-Enum?
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!
      Hab angenommen didaktisch wäre das nützlicher. Es kann ja auch vorkommen das jemand aus der Java Programmierung hier vorbeischaut.. ist für ihn eventualiter einfacher nachzuvollziehen.

      Grüße
      Und Gott alleine weiß alles am allerbesten und besser.