Mod von Power 2 auf bitweise Operatoren?

Lesezeit: 3 Minuten

Benutzeravatar von Zo Has
Zo hat

  1. Wie funktioniert mod of power of 2 nur bei niederwertigen Bits einer Binärzahl (1011000111011010)?
  2. Was ist diese Zahl mod 2 hoch 0, 2 hoch 4?
  3. Was hat die Zweierpotenz mit dem Modulo-Operator zu tun? Hat es eine besondere Eigenschaft?
  4. Kann mir jemand ein Beispiel geben?

Der Ausbilder sagt: “Wenn Sie etwas Mod zur Potenz von 2 nehmen, nehmen Sie einfach die Bits niedrigerer Ordnung”. Ich hatte zu viel Angst zu fragen, was er meinte =)

  • Probieren Sie doch mal ein paar Beispielrechnungen per Hand aus, dann sehen Sie, was passiert.

    – sternenblau

    13. Juli 2011 um 10:20 Uhr

Er meinte das Nehmen number mod 2^n ist gleichbedeutend mit dem Abstreifen aller außer der n niedrigste Ordnung (ganz rechts) Stücke von number.

Wenn zum Beispiel n == 2,

number      number mod 4
00000001      00000001
00000010      00000010
00000011      00000011
00000100      00000000
00000101      00000001
00000110      00000010
00000111      00000011
00001000      00000000
00001001      00000001
etc.

Also mit anderen Worten, number mod 4 ist das gleiche wie number & 00000011 (wo & bedeutet bitweise-und)


Beachten Sie, dass dies in base-10 genauso funktioniert: number mod 10 gibt Ihnen die letzte Ziffer der Zahl in Basis-10, number mod 100 gibt Ihnen die letzten beiden Ziffern usw.

  • Dies ist nur der Fall, wenn alle Operanden positiv sind! Je nach Sprache unterscheidet sich das Verhalten. Zum Beispiel in C, -5 % 4 == -1 obwohl wir das in der Algebra normalerweise erwarten -5 mod 4 ist 3 (und in C: -5 & (4 - 1) == 3. Das bedeutet zum Beispiel, dass ein Compiler ein Literal nicht optimiert % 4 mit einer & wenn der linke Operand nicht vorzeichenlos ist.

    – Calandoa

    18. November 2016 um 15:46 Uhr


  • @calandoa: Wir diskutieren hier binär als Zahlensystem, nicht die Bitcodierung von Zahlen. -5wird zum Beispiel geschrieben -101.

    – BlueRaja – Danny Pflughöft

    18. November 2016 um 16:08 Uhr


  • @BlueRaja: Natürlich sprechen wir über Bitcodierung: & ist nicht für mathematisch definiert -. Ich denke, Ihre Bemerkung ist eher “wir sprechen nicht über negative Zahlen”. Vielleicht sind wir das nicht, aber das ist weder in der Frage noch in Ihrer Antwort klar, also habe ich es klarer gemacht.

    – Calandoa

    22. November 2016 um 11:18 Uhr

  • Machst du so etwas wie number MOD 256 <=> (number & (0xFF00)) >> 8 (für 2^8 = 256)

    – Sandburg

    26. November 2019 um 15:29 Uhr


Benutzeravatar von user703016
Benutzer703016

Was er meint ist folgendes:

x modulo y = (x & (y − 1))

Wenn y eine Potenz von 2 ist.

Beispiel:

0110010110 (406) modulo
0001000000 (64)  =
0000010110 (22)
^^^^<- ignore these bits

Jetzt mit deinem Beispiel:

1011000111011010 (45530) modulo
0000000000000001 (2 power 0) =
0000000000000000 (0)
^^^^^^^^^^^^^^^^<- ignore these bits

1011000111011010 (45530) modulo
0000000000010000 (2 power 4) =
0000000000001010 (10)
^^^^^^^^^^^^<- ignore these bits

  • Hey danke für die Antwort. Ich habe dein Beispiel nicht ganz verstanden?

    – Zo hat

    12. Juli 2011 um 20:36 Uhr

Betrachten Sie, wenn Sie eine Zahl modulo 10 nehmen. Wenn Sie das tun, erhalten Sie nur die letzte Ziffer der Zahl.

  334 % 10 = 4
  12345 % 10 = 5

Wenn Sie eine Zahl modulo 100 nehmen, erhalten Sie ebenfalls nur die letzten beiden Ziffern.

  334 % 100 = 34
  12345 % 100 = 45

Sie können also den Modulo einer Zweierpotenz erhalten, indem Sie sich die letzten Ziffern in Binärform ansehen. Das ist dasselbe wie ein bitweises und.

  • Gilt das auch für Zweierpotenzen? 54 % 32, was 2^5 ergibt, ergibt 22.

    – Zo hat

    12. Juli 2011 um 21:07 Uhr

  • Popo: Ja. Die Anzahl der Bits am Ende wird durch die verwendete Zweierpotenz bestimmt. Wie von Cicada beschrieben, würden Sie es als 54 & (32-1) berechnen.

    – Brian

    12. Juli 2011 um 21:39 Uhr

Modulo gibt im Allgemeinen den Rest eines Werts nach der Division zurück. So x mod 4, gibt zum Beispiel 0, 1, 2 oder 3 abhängig von x zurück. Diese möglichen Werte können mit zwei binären Bits (00, 01, 10, 11) dargestellt werden – eine andere Möglichkeit x mod 4 besteht darin, einfach alle Bits in x auf Null zu setzen, mit Ausnahme der letzten beiden.

Beispiel:

      x = 10101010110101110
x mod 4 = 00000000000000010

Beantwortung Ihrer konkreten Fragen:

  1. mod ist ein Restoperator. Wenn es auf eine Reihe von Zahlen x in 0, 1, … angewendet wird, dann ist x mod n 0, 1, …, n-1, 0, 1, …, n-1, ad infinitum. Wenn Ihr Modulus n eine Potenz von 2 ist, dann zählt x mod n binär von 0 bis n-1, zurück zu 0, zu n-1 usw.; für modulus n, das wie binär 01xxxxx aussieht, durchläuft x mod n jedes dieser niederwertigen Bits xxxxx.
  2. binär 1011000111011010 mod 1 ist 0 (mod 2^0 ergibt die letzten Nullbits; alles mod 1 ist null). binär 1011000111011010 mod binär 10000 ist 1010 (mod 2^4 ergibt die letzten vier Bits).
  3. Die Division und der Rest der Binärzahl durch Zweierpotenzen ist besonders effizient, da es sich nur um eine Verschiebung und Maskierung handelt; mathematisch ist es nichts Besonderes.
  4. Beispiel: Siehe Antwort zu Frage 2.

1408180cookie-checkMod von Power 2 auf bitweise Operatoren?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy