Mengapa (a% 256) berbeda dari (a & 0xFF)?

Saya selalu berasumsi bahwa ketika melakukan (a % 256)pengoptimal akan secara alami menggunakan operasi bitwise yang efisien, seolah-olah saya menulis (a & 0xFF).

Saat menguji pada compiler explorer gcc-6.2 (-O3):

// Type your code here, or load an example.
int mod(int num) {
    return num % 256;
}

mod(int):
    mov     edx, edi
    sar     edx, 31
    shr     edx, 24
    lea     eax, [rdi+rdx]
    movzx   eax, al
    sub     eax, edx
    ret

Dan ketika mencoba kode lainnya:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Sepertinya saya benar-benar kehilangan sesuatu. Ada ide?

Ini tidak sama. Coba num = -79, dan Anda akan mendapatkan hasil yang berbeda dari kedua operasi. (-79) % 256 = -79, sedangkan (-79) & 0xffbeberapa angka positif.

Dengan menggunakan unsigned int, operasinya sama, dan kode kemungkinan akan sama.

PS- Seseorang berkomentar

Mereka tidak boleh sama, a % bdidefinisikan sebagai a - b * floor (a / b).

Itu bukan bagaimana itu didefinisikan dalam C, C ++, Objective-C (yaitu semua bahasa di mana kode dalam pertanyaan akan dikompilasi).

Jawaban singkat

-1 % 256hasil -1dan bukan 255yang mana -1 & 0xFF. Karena itu, optimasi akan salah.

Jawaban panjang

C ++ memiliki konvensi itu (a/b)*b + a%b == a, yang tampaknya cukup alami. a/bselalu mengembalikan hasil aritmatika tanpa bagian fraksional (memotong menuju 0). Akibatnya, a%bmemiliki tanda yang sama dengan aatau adalah 0.

Divisi -1/256menghasilkan 0dan karenanya -1%256harus -1memenuhi persyaratan di atas ( (-1%256)*256 + -1%256 == -1). Ini jelas berbeda dari -1&0xFFyang mana 0xFF. Oleh karena itu, kompiler tidak dapat mengoptimalkan seperti yang Anda inginkan.

Bagian yang relevan dalam standar C ++ [expr.mul §4] pada N4606 menyatakan:

Untuk operan integral /operator menghasilkan hasil bagi aljabar dengan setiap bagian pecahan dibuang; jika hasil bagi a/bdiwakili dalam jenis hasil, (a/b)*b + a%bsama dengan a[...].

Mengaktifkan pengoptimalan

Namun, menggunakan unsignedtipe, optimisasi akan sepenuhnya benar , memenuhi konvensi di atas:

unsigned(-1)%256 == 0xFF

Lihat juga ini .

Bahasa lainnya

Ini ditangani sangat berbeda di berbagai bahasa pemrograman karena Anda dapat melihat di Wikipedia .

Sejak C ++ 11, num % 256harus non-positif jika numnegatif.

Jadi pola bit akan tergantung pada implementasi tipe yang ditandatangani pada sistem Anda: untuk argumen pertama yang negatif, hasilnya bukan ekstraksi dari 8 bit yang paling tidak signifikan.

Ini akan menjadi masalah yang berbeda jika numdalam kasus Anda adalah unsigned: hari ini saya hampir berharap kompiler membuat optimasi yang Anda kutip.

Saya tidak memiliki wawasan telepati ke dalam alasan kompiler, tetapi dalam kasus %ada perlunya berurusan dengan nilai-nilai negatif (dan putaran pembagian ke nol), sementara dengan &hasilnya selalu 8 bit yang lebih rendah.

The sarinstruksi suara untuk saya seperti "bergeser ke kanan aritmatika", mengisi bit dikosongkan dengan nilai tanda bit.

Secara matematis, modulo didefinisikan sebagai berikut:

a% b = a - b * lantai (a / b)

Ini di sini harus menjelaskannya untuk Anda. Kita dapat menghilangkan lantai untuk bilangan bulat karena pembagian bilangan bulat setara dengan lantai (a / b). Namun, jika kompiler menggunakan trik umum seperti yang Anda sarankan, itu perlu bekerja untuk semua dan semua b. Sayangnya, ini bukan masalahnya. Secara matematis, trik Anda 100% benar untuk bilangan bulat yang tidak ditandatangani (Saya melihat jawaban menyatakan bilangan bulat yang ditandatangani rusak, tetapi saya dapat mengonfirmasi atau menolak ini karena -a% b harus positif). Namun, dapatkah Anda melakukan trik ini untuk semua b? Mungkin tidak. Itu sebabnya kompiler tidak melakukannya. Lagi pula, jika modulo mudah ditulis sebagai satu operasi bitwise, maka kita hanya akan menambahkan rangkaian modulo seperti untuk penambahan dan operasi lainnya.