Bitwise dan menggantikan operator modulus

Kita tahu bahwa misalnya modulo kekuatan dua dapat diekspresikan seperti ini:

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

Contoh:

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

Bagaimana dengan nonpower umum dari dua angka?

Katakanlah:

x% 7 ==?

Pertama-tama, sebenarnya tidak tepat untuk mengatakannya

x % 2 == x & 1

Counterexample sederhana: x = -1. Dalam banyak bahasa, termasuk Java -1 % 2 == -1,. Artinya, %belum tentu definisi matematika tradisional dari modulo. Java menyebutnya "operator sisa", misalnya.

Berkenaan dengan pengoptimalan bitwise, hanya dua kekuatan modulo yang dapat "dengan mudah" dilakukan dalam aritmatika bitwise. Secara umum, hanya kekuatan modulo dari basis b yang dapat "dengan mudah" dilakukan dengan representasi angka basis b .

Dalam basis 10, misalnya, untuk non-negatif N, N mod 10^khanya mengambil angka paling signifikan k.

Referensi

• JLS 15.17.3 Operator Sisa%
• Operasi Wikipedia / Modulo

Hanya ada cara sederhana untuk menemukan modulo bilangan 2 ^ i menggunakan bitwise.

Ada cara cerdik untuk menyelesaikan kasus Mersenne sesuai dengan tautan seperti n% 3, n% 7 ... Ada kasus khusus untuk n% 5, n% 255, dan kasus komposit seperti n% 6.

Untuk kasus 2 ^ i, (2, 4, 8, 16 ...)

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

Yang lebih rumit sulit dijelaskan. Bacalah hanya jika Anda sangat penasaran.

Ini hanya berfungsi untuk pangkat dua (dan seringkali hanya yang positif) karena mereka memiliki properti unik yang hanya memiliki satu bit yang disetel ke '1' dalam representasi binernya. Karena tidak ada kelas bilangan lain yang berbagi properti ini, Anda tidak dapat membuat bitwise-dan ekspresi untuk sebagian besar ekspresi modulus.

Ini secara khusus merupakan kasus khusus karena komputer mewakili angka di basis 2. Ini dapat digeneralisasikan:

(angka) _basis % basis ^x

setara dengan digit x terakhir dari (bilangan) _basis .

Ada modulus selain pangkat 2 yang memiliki algoritme efisien.

Misalnya, jika x adalah 32 bit unsigned int maka x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Modulo "7" tanpa operator "%"

int a = x % 7;

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

Tidak menggunakan bitwise-dan (& operator ) dalam biner, tidak ada. Sketsa bukti:

Misalkan ada nilai k sedemikian rupa x & k == x % (k + 1), tetapi k! = 2 ^ n - 1 . Kemudian jika x == k , pernyataan tersebut x & ktampaknya "beroperasi dengan benar" dan hasilnya adalah k . Sekarang, pertimbangkan x == ki : jika ada bit "0" di k , ada beberapa i lebih besar dari 0 yang ki hanya dapat diekspresikan dengan 1-bit pada posisi tersebut. (Misalnya, 1011 (11) harus menjadi 0111 (7) ketika 100 (4) telah dikurangi darinya, dalam hal ini 000 bit menjadi 100 ketika i = 4. ) Jika sedikit dari ekspresi k harus berubah dari nol ke satu untuk mewakili ki, maka itu tidak dapat menghitung dengan benar x% (k + 1) , yang dalam hal ini seharusnya ki , tetapi tidak ada cara untuk bitwise boolean dan untuk menghasilkan nilai tersebut dengan menggunakan mask.

Dalam kasus khusus ini (mod 7), kami masih dapat mengganti% 7 dengan operator bitwise:

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

Ia bekerja karena 8% 7 = 1. Jelas, kode ini mungkin kurang efisien daripada x% 7 sederhana, dan tentunya kurang dapat dibaca.

Dengan menggunakan bitwise_and, bitwise_or, dan bitwise_not Anda dapat mengubah konfigurasi bit apa pun ke konfigurasi bit lain (yaitu, rangkaian operator ini "berfungsi lengkap"). Namun, untuk operasi seperti modulus, rumus umum akan menjadi sangat rumit, saya bahkan tidak akan repot-repot mencoba membuatnya kembali.