Opsi mana yang lebih baik untuk digunakan untuk membagi angka integer dengan 2?

Manakah dari teknik berikut ini yang merupakan pilihan terbaik untuk membagi bilangan bulat dengan 2 dan mengapa?

Teknik 1:

x = x >> 1;

Teknik 2:

x = x / 2;

Berikut xini adalah bilangan bulat.

Gunakan operasi yang paling menggambarkan apa yang Anda coba lakukan.

• Jika Anda memperlakukan nomor sebagai urutan bit, gunakan bithift.
• Jika Anda memperlakukannya sebagai nilai numerik, gunakan pembagian.

Perhatikan bahwa mereka tidak persis setara. Mereka dapat memberikan hasil yang berbeda untuk bilangan bulat negatif. Sebagai contoh:

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

Apakah yang pertama terlihat seperti membagi? Tidak. Jika Anda ingin membelah, gunakan x / 2. Kompiler dapat mengoptimalkannya untuk menggunakan bit-shift jika memungkinkan (ini disebut pengurangan kekuatan), yang membuatnya menjadi optimasi mikro yang tidak berguna jika Anda melakukannya sendiri.

Untuk menimbun: ada begitu banyak alasan untuk memilih menggunakan x = x / 2; Berikut adalah beberapa:

• itu mengekspresikan maksud Anda lebih jelas (dengan asumsi Anda tidak berurusan dengan bit twiddling register bit atau sesuatu)

• kompiler akan mengurangi ini ke operasi shift

• bahkan jika kompilator tidak menguranginya dan memilih operasi yang lebih lambat daripada shift, kemungkinan bahwa ini pada akhirnya mempengaruhi kinerja program Anda dengan cara yang terukur itu sendiri semakin kecil (dan jika itu memengaruhi itu secara terukur, maka Anda memiliki aktual alasan untuk menggunakan shift)

• jika divisi akan menjadi bagian dari ekspresi yang lebih besar, Anda lebih mungkin mendapatkan hak diutamakan jika Anda menggunakan operator divisi:

  x = x / 2 + 5;
  x = x >> 1 + 5;  // not the same as above

• aritmatika yang ditandatangani dapat mempersulit hal-hal bahkan lebih dari masalah yang diutamakan yang disebutkan di atas

• untuk mengulangi - kompiler akan tetap melakukan ini untuk Anda. Bahkan, itu akan mengkonversi pembagian dengan konstan ke serangkaian shift, tambah, dan dikalikan untuk semua jenis angka, bukan hanya kekuatan dua. Lihat pertanyaan ini untuk tautan ke informasi lebih lanjut tentang ini.

Singkatnya, Anda tidak membeli apa pun dengan mengkodekan perubahan saat Anda benar-benar bermaksud melipatgandakan atau membagi, kecuali kemungkinan peningkatan kemungkinan memperkenalkan bug. Sudah seumur hidup sejak kompiler tidak cukup pintar untuk mengoptimalkan hal semacam ini ke shift saat yang tepat.

Yang mana merupakan opsi terbaik dan mengapa untuk membagi angka integer dengan 2?

Tergantung pada apa yang Anda maksud dengan yang terbaik .

Jika Anda ingin kolega Anda membenci Anda, atau membuat kode Anda sulit dibaca, saya pasti akan memilih opsi pertama.

Jika Anda ingin membagi angka dengan 2, lanjutkan dengan yang kedua.

Keduanya tidak setara, mereka tidak berperilaku sama jika jumlahnya negatif atau di dalam ekspresi yang lebih besar - bitshift memiliki prioritas lebih rendah daripada +atau -, divisi memiliki prioritas lebih tinggi.

Anda harus menulis kode Anda untuk mengungkapkan maksudnya. Jika kinerja menjadi perhatian Anda, jangan khawatir, pengoptimal melakukan pekerjaan dengan baik pada optimasi mikro semacam ini.

Cukup gunakan divide ( /), anggap itu lebih jelas. Kompiler akan mengoptimalkannya.

Saya setuju dengan jawaban lain yang harus Anda sukai x / 2karena maksudnya lebih jelas, dan kompiler harus mengoptimalkannya untuk Anda.

Namun, alasan lain untuk memilih x / 2lebih x >> 1adalah bahwa perilaku >>adalah implementasi tergantung jika xadalah ditandatangani intdan negatif.

Dari bagian 6.5.7, bullet 5 dari standar ISO C99:

Hasil E1 >> E2ini E1benar-bergeser E2posisi bit. Jika E1memiliki tipe yang tidak ditandatangani atau jika E1memiliki tipe yang ditandatangani dan nilai yang tidak negatif, nilai hasilnya adalah bagian integral dari hasil bagi E1/ 2 ^E2. Jika E1memiliki tipe yang ditandatangani dan nilai negatif, nilai yang dihasilkan ditentukan oleh implementasi.

x / 2lebih jelas, dan x >> 1tidak jauh lebih cepat (menurut tolok ukur mikro, sekitar 30% lebih cepat untuk Java JVM). Seperti yang telah dicatat orang lain, untuk bilangan negatif pembulatannya sedikit berbeda, jadi Anda harus mempertimbangkan ini ketika Anda ingin memproses bilangan negatif. Beberapa kompiler dapat secara otomatis dikonversi x / 2ke x >> 1jika mereka tahu nomornya tidak boleh negatif (bahkan saya pikir saya tidak dapat memverifikasi ini).

Bahkan x / 2mungkin tidak menggunakan instruksi CPU divisi (lambat), karena beberapa pintasan dimungkinkan , tetapi masih lebih lambat dari itu x >> 1.

(Ini adalah pertanyaan C / C ++, bahasa pemrograman lain memiliki lebih banyak operator. Untuk Java juga ada pergeseran kanan yang tidak ditandai x >>> 1, yang lagi-lagi berbeda. Memungkinkan untuk menghitung dengan benar nilai rata-rata (rata-rata) dari dua nilai, sehingga (a + b) >>> 1akan mengembalikan nilai rata-rata bahkan untuk nilai yang sangat besar dari adan b. Ini diperlukan misalnya untuk pencarian biner jika indeks array bisa menjadi sangat besar. Ada bug di banyak versi pencarian biner , karena mereka digunakan (a + b) / 2untuk menghitung rata-rata. tidak berfungsi dengan benar. Solusi yang tepat adalah dengan menggunakan (a + b) >>> 1.)

Knuth berkata:

Optimalisasi prematur adalah akar dari semua kejahatan.

Jadi saya sarankan untuk digunakan x /= 2;

Dengan cara ini kodenya mudah dimengerti dan saya juga berpikir bahwa optimalisasi operasi ini dalam bentuk itu, tidak berarti perbedaan besar untuk prosesor.

Lihatlah output kompiler untuk membantu Anda memutuskan. Saya menjalankan tes ini pada x86-64 dengan
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Juga lihat output kompiler online di godbolt .

Apa yang Anda lihat adalah kompiler tidak menggunakan sarlinstruksi (aritmatik pergeseran kanan) dalam kedua kasus, sehingga ia mengenali kesamaan antara dua ekspresi. Jika Anda menggunakan pembagian, kompiler juga perlu menyesuaikan untuk angka negatif. Untuk melakukan itu menggeser bit tanda ke bit urutan terendah, dan menambahkannya ke hasilnya. Ini memperbaiki masalah off-by-one ketika menggeser angka negatif, dibandingkan dengan apa yang akan dilakukan pembagian.
Karena case divide melakukan 2 shift, sementara case shift eksplisit hanya melakukan satu shift, kita sekarang dapat menjelaskan beberapa perbedaan kinerja yang diukur dengan jawaban lain di sini.

Kode C dengan output perakitan:

Untuk membagi, input Anda adalah

int div2signed(int a) {
  return a / 2;
}

dan ini mengkompilasi ke

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

sama untuk shift

int shr2signed(int a) {
  return a >> 1;
}

dengan output:

    sarl    %edi
    movl    %edi, %eax
    ret

Hanya catatan tambahan -

x * = 0,5 akan sering lebih cepat dalam beberapa bahasa berbasis VM - terutama actioncript, karena variabel tidak harus diperiksa untuk membagi dengan 0.

Gunakan x = x / 2; ATAU x /= 2;Karena ada kemungkinan bahwa programmer baru bekerja di masa depan. Jadi akan lebih mudah baginya untuk mencari tahu apa yang terjadi di dalam barisan kode. Semua orang mungkin tidak mengetahui optimasi seperti itu.

Saya mengatakan untuk tujuan kompetisi pemrograman. Umumnya mereka memiliki input yang sangat besar di mana pembagian oleh 2 terjadi berkali-kali dan diketahui bahwa inputnya positif atau negatif.

x >> 1 akan lebih baik dari x / 2. Saya memeriksa ideone.com dengan menjalankan program di mana lebih dari 10 ^ 10 divisi dengan 2 operasi berlangsung. x / 2 mengambil hampir 5,5 sedangkan x >> 1 mengambil hampir 2,6 untuk program yang sama.

Saya akan mengatakan ada beberapa hal yang perlu dipertimbangkan.

1. Bitshift harus lebih cepat, karena tidak ada perhitungan khusus yang benar-benar diperlukan untuk menggeser bit, namun seperti yang ditunjukkan, ada masalah potensial dengan angka negatif. Jika Anda dipastikan memiliki angka positif, dan sedang mencari kecepatan maka saya akan merekomendasikan bitshift.

2. Operator divisi sangat mudah bagi manusia untuk membaca. Jadi jika Anda mencari pembacaan kode, Anda bisa menggunakan ini. Perhatikan bahwa bidang optimisasi kompiler telah jauh, sehingga membuat kode mudah dibaca dan dipahami adalah praktik yang baik.

3. Tergantung pada perangkat keras yang mendasarinya, operasi mungkin memiliki kecepatan yang berbeda. Hukum Amdal adalah untuk membuat kasus umum cepat. Jadi, Anda mungkin memiliki perangkat keras yang dapat melakukan berbagai operasi lebih cepat daripada yang lain. Misalnya, mengalikan dengan 0,5 mungkin lebih cepat daripada membagi dengan 2. (Memang Anda mungkin perlu mengambil dasar perkalian jika Anda ingin menegakkan pembagian bilangan bulat).

Jika Anda mengejar kinerja murni, saya akan merekomendasikan membuat beberapa tes yang dapat melakukan operasi jutaan kali. Contoh eksekusi beberapa kali (ukuran sampel Anda) untuk menentukan mana yang terbaik secara statistik dengan OS / Perangkat Keras / Kompiler / Kode Anda.

Sejauh menyangkut CPU, operasi bit-shift lebih cepat daripada operasi divisi. Namun, kompiler mengetahui hal ini dan akan mengoptimalkan secara tepat sejauh mungkin, sehingga Anda dapat membuat kode dengan cara yang paling masuk akal dan mudah mengetahui bahwa kode Anda berjalan secara efisien. Tetapi ingat bahwa suatu unsigned intkaleng (dalam beberapa kasus) dapat dioptimalkan lebih baik daripada suatu intkarena alasan yang disebutkan sebelumnya. Jika Anda tidak perlu masuk aritmatika, maka jangan sertakan bit tanda.

x = x / 2; adalah kode yang cocok untuk digunakan .. tetapi operasi tergantung pada program Anda sendiri tentang bagaimana output yang ingin Anda hasilkan.

Jadikan niat Anda lebih jelas ... misalnya, jika Anda ingin membagi, gunakan x / 2, dan biarkan kompilator mengoptimalkannya untuk menggeser operator (atau apa pun).

Prosesor hari ini tidak akan membiarkan pengoptimalan ini berdampak pada kinerja program Anda.

Jawabannya tergantung pada lingkungan tempat Anda bekerja.

• Jika Anda bekerja pada mikrokontroler 8-bit atau apa pun tanpa dukungan perangkat keras untuk penggandaan, diharapkan pergeseran bit dan hal biasa, dan sementara kompiler hampir pasti akan berubah x /= 2menjadi x >>= 1, kehadiran simbol divisi akan menaikkan lebih banyak alis di lingkungan itu daripada menggunakan shift untuk melakukan pembagian.
• Jika Anda bekerja di lingkungan yang kritis terhadap kinerja atau bagian kode, atau kode Anda dapat dikompilasi dengan optimisasi kompiler dimatikan, x >>= 1dengan komentar yang menjelaskan alasannya mungkin yang terbaik hanya untuk kejelasan tujuan.
• Jika Anda tidak berada di bawah salah satu kondisi di atas, buat kode Anda lebih mudah dibaca hanya dengan menggunakan x /= 2. Lebih baik menyelamatkan programmer berikutnya yang kebetulan melihat kode Anda 10 detik untuk operasi shift Anda daripada membuktikan bahwa Anda tahu perubahan itu lebih efisien daripada optimasi kompiler.

Semua ini mengasumsikan bilangan bulat yang tidak ditandatangani. Pergeseran sederhana mungkin bukan yang Anda inginkan untuk ditandatangani. Juga, DanielH membawa poin bagus tentang penggunaan x *= 0.5untuk bahasa tertentu seperti ActionScript.

mod 2, tes untuk = 1. tidak tahu sintaks di c. tapi ini mungkin yang tercepat.

umumnya shift kanan dibagi:

q = i >> n; is the same as: q = i / 2**n;

ini kadang-kadang digunakan untuk mempercepat program dengan biaya kejelasan. Saya tidak berpikir Anda harus melakukannya. Kompiler cukup pintar untuk melakukan speedup secara otomatis. Ini berarti bahwa menempatkan perubahan tidak memberi Anda keuntungan apa pun dengan mengorbankan kejelasan .

Lihatlah halaman ini dari Pemrograman C ++ Praktis.

Jelas, jika Anda menulis kode Anda untuk orang berikutnya yang membacanya, cari kejelasan "x / 2".

Namun, jika kecepatan adalah tujuan Anda, cobalah baik cara dan waktu hasilnya. Beberapa bulan yang lalu saya mengerjakan sebuah rutin konvolusi bitmap yang melibatkan melangkah melalui array bilangan bulat dan membagi masing-masing elemen dengan 2. Saya melakukan segala macam hal untuk mengoptimalkannya termasuk trik lama untuk mengganti "x >> 1" untuk "x / 2 ".

Ketika saya benar-benar menghitung waktu kedua cara saya menemukan saya terkejut bahwa x / 2 lebih cepat dari x >> 1

Ini menggunakan Microsoft VS2008 C ++ dengan optimasi default dihidupkan.

Dari segi kinerja. Operasi shift CPU secara signifikan lebih cepat daripada membagi kode-op. Jadi membagi dengan dua atau mengalikan dengan 2 dll semua mendapat manfaat dari operasi shift.

Seperti untuk tampilan dan nuansa. Sebagai insinyur kapan kita menjadi begitu terikat pada kosmetik yang bahkan wanita cantik tidak gunakan! :)

X / Y adalah yang benar ... dan operator pemindahan ">>" ..jika kita ingin dua membagi bilangan bulat kita dapat menggunakan (/) operator dividen. operator shift digunakan untuk menggeser bit ..

x = x / 2; x / = 2; bisa kita gunakan seperti ini ..

Sementara x >> 1 lebih cepat dari x / 2, penggunaan yang tepat >> ketika berhadapan dengan nilai negatif sedikit lebih rumit. Dibutuhkan sesuatu yang mirip dengan yang berikut:

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}