Bitweise und anstelle des Moduloperators

Wir wissen, dass zum Beispiel das Modulo der Potenz von zwei folgendermaßen ausgedrückt werden kann:

  x % 2 inpower n == x & (2 inpower n - 1).

Beispiele:

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7 

Was ist mit der allgemeinen Nichtkraft zweier Zahlen?

Sagen wir:

x% 7 ==?

Erstens ist es eigentlich nicht richtig, das zu sagen

x % 2 == x & 1

Einfaches Gegenbeispiel : x = -1. In vielen Sprachen, einschließlich Java -1 % 2 == -1. Das ist,% ist nicht unbedingt die traditionelle mathematische Definition von Modulo. Java nennt es zum Beispiel den "Restoperator".

In Bezug auf die bitweise Optimierung können in der bitweisen Arithmetik nur Modulo-Potenzen von zwei "leicht" durchgeführt werden. Im Allgemeinen nur Modulo Kräfte der Basis b können „leicht“ mit Basis erfolgen b Darstellung von Zahlen.

In der Basis 10, beispielsweise für nicht-negative N, N mod 10^knimmt nur die am wenigsten signifikanten kZiffern.

Verweise

• JLS 15.17.3 Restbetreiber%
• Wikipedia / Modulo Betrieb

Es gibt nur eine einfache Möglichkeit , das Modulo von 2 ^ i-Zahlen bitweise zu finden.

Es gibt eine geniale Möglichkeit, Mersenne- Fälle gemäß dem Link zu lösen, z. B. n% 3, n% 7 ... Es gibt Sonderfälle für n% 5, n% 255 und zusammengesetzte Fälle wie n% 6.

Für die Fälle 2 ^ i, (2, 4, 8, 16 ...)

n % 2^i = n & (2^i - 1)

Kompliziertere sind schwer zu erklären. Lesen Sie nur, wenn Sie sehr neugierig sind.

Dies funktioniert nur für Zweierpotenzen (und häufig nur für positive), da sie die einzigartige Eigenschaft haben, in ihrer Binärdarstellung nur ein Bit auf '1' zu setzen. Da keine andere Zahlenklasse diese Eigenschaft gemeinsam hat, können Sie für die meisten Modulausdrücke keine bitweisen Ausdrücke erstellen.

Dies ist speziell ein Sonderfall, da Computer Zahlen in Basis 2 darstellen. Dies ist verallgemeinerbar:

(Anzahl) _Basis % Basis ^x

entspricht den letzten x Ziffern der (Zahlen-) _Basis .

Es gibt andere Module als Zweierpotenzen, für die effiziente Algorithmen existieren.

Wenn x beispielsweise 32 Bit ohne Vorzeichen int ist, ist x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Modulo "7" ohne "%" Operator

int a = x % 7;

int a = (x + x / 7) & 7;

Wenn der &Operator bitwise-and ( ) nicht binär verwendet wird, gibt es keinen. Beweisskizze:

Angenommen, es gäbe einen solchen Wert kx & k == x % (k + 1) , aber k! = 2 ^ n - 1 . Wenn dann x == k ist , x & kscheint der Ausdruck "korrekt zu funktionieren" und das Ergebnis ist k . Betrachten wir nun x == ki : Wenn es in k "0" -Bits gibt, gibt es einige i größer als 0, die ki nur mit 1-Bits an diesen Positionen ausgedrückt werden kann. (ZB muss 1011 (11) 0111 (7) werden, wenn 100 (4) davon subtrahiert wurde. In diesem Fall wird das 000-Bit 100, wenn i = 4. ) Wenn sich ein Bit aus dem Ausdruck von k von Null ändern muss zu einem, um ki darzustellendann kann es x% (k + 1) nicht korrekt berechnen , was in diesem Fall ki sein sollte , aber es gibt keine Möglichkeit, bitweise boolesch zu sein und diesen Wert unter Berücksichtigung der Maske zu erzeugen.

In diesem speziellen Fall (Mod 7) können wir% 7 immer noch durch bitweise Operatoren ersetzen:

// Return X%7 for X >= 0.
int mod7(int x)
{
  while (x > 7) x = (x&7) + (x>>3);
  return (x == 7)?0:x;
}

Es funktioniert, weil 8% 7 = 1. Offensichtlich ist dieser Code wahrscheinlich weniger effizient als ein einfacher x% 7 und sicherlich weniger lesbar.

Mit bitwise_and, bitwise_or und bitwise_not können Sie beliebige Bitkonfigurationen in andere Bitkonfigurationen ändern (dh diese Operatoren sind "funktional vollständig"). Für Operationen wie den Modul wäre die allgemeine Formel jedoch notwendigerweise ziemlich kompliziert, ich würde nicht einmal versuchen, sie neu zu erstellen.