Bitowo i zamiast operatora modułu

Wiemy, że na przykład modulo potęgi dwóch można wyrazić w ten sposób:

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

Przykłady:

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

A co z ogólną niepotęgą dwóch liczb?

Powiedzmy:

x% 7 ==?

Po pierwsze, tak naprawdę nie jest to prawdą

x % 2 == x & 1

Proste kontrprzykład: x = -1. W wielu językach, w tym Java -1 % 2 == -1. Oznacza to, że %niekoniecznie jest to tradycyjna matematyczna definicja modulo. Na przykład Java nazywa to „operatorem reszty”.

Jeśli chodzi o optymalizację bitową, tylko potęgi modulo równe dwóm można „łatwo” wykonać w arytmetyce bitowej. Ogólnie mówiąc, tylko potęgi modulo o podstawie b można „łatwo” wykonać z reprezentacją liczb o podstawie b .

W bazie 10, na przykład, dla nieujemnych N, N mod 10^kjest po prostu biorąc najmniej znaczących kcyfr.

Bibliografia

• JLS 15.17.3 Pozostały operator%
• Wikipedia / Modulo Operation

Jest tylko prosty sposób na znalezienie modulo 2 ^ i liczb za pomocą bitów.

Istnieje genialny sposób rozwiązywania przypadków Mersenne'a zgodnie z linkiem, takim jak n% 3, n% 7 ... Istnieją specjalne przypadki dla n% 5, n% 255 i przypadki złożone, takie jak n% 6.

W przypadkach 2 ^ i, (2, 4, 8, 16 ...)

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

Bardziej skomplikowane są trudne do wyjaśnienia. Czytaj tylko, jeśli jesteś bardzo ciekawy.

Działa to tylko dla potęg dwójki (i często tylko dodatnich), ponieważ mają one unikalną właściwość posiadania tylko jednego bitu ustawionego na „1” w ich binarnej reprezentacji. Ponieważ żadna inna klasa liczb nie ma tej właściwości, nie można tworzyć wyrażeń bitowych i dla większości wyrażeń modułu.

Jest to szczególnie szczególny przypadek, ponieważ komputery reprezentują liczby o podstawie 2. Można to uogólnić:

(liczba) _podstawa % podstawa ^x

jest równy ostatnim x cyfrom _podstawy (liczby) .

Istnieją moduły inne niż potęgi 2, dla których istnieją wydajne algorytmy.

Na przykład, jeśli x to 32 bity bez znaku int, a następnie x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Modulo „7” bez operatora „%”

int a = x % 7;

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

Nieużywanie bitowych i (& operatora ) w systemie binarnym, nie ma. Szkic dowodu:

Załóżmy, że było wartością K w taki sposób, x & k == x % (k + 1)ale K = 2 ^ n - 1 . Wtedy, jeśli x == k , wyrażenie x & kwydaje się „działać poprawnie”, a wynikiem jest k . Rozważmy teraz x == ki : jeśli w k było jakieś „0” bitów , istnieje i większe od 0, które ki może być wyrażone tylko za pomocą 1-bitów w tych pozycjach. (Np. 1011 (11) musi stać się 0111 (7) po odjęciu od niego 100 (4), w tym przypadku bit 000 staje się 100, gdy i = 4 ). Jeśli bit z wyrażenia k musi zmienić się od zera do jednego, który reprezentuje ki, to nie może poprawnie obliczyć x% (k + 1) , co w tym przypadku powinno być ki , ale nie ma sposobu na bitowe wartości logiczne i uzyskanie tej wartości podanej masce.

W tym konkretnym przypadku (mod 7) nadal możemy zastąpić% 7 operatorami bitowymi:

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

Działa, ponieważ 8% 7 = 1. Oczywiście ten kod jest prawdopodobnie mniej wydajny niż zwykły x% 7 iz pewnością mniej czytelny.

Używając bitwise_and, bitwise_or i bitwise_not można modyfikować dowolne konfiguracje bitów na inne konfiguracje bitowe (tj. Te zestawy operatorów są „funkcjonalnie kompletne”). Jednak w przypadku operacji takich jak moduł ogólny wzór byłby z konieczności dość skomplikowany, nawet nie zawracałbym sobie głowy próbą odtworzenia go.