Apakah operator shift (<<, >>) aritmatika atau logis dalam C?

Jawaban:

97

Menurut K&R edisi ke-2 , hasilnya tergantung pada implementasi untuk pergeseran yang tepat dari nilai yang ditandatangani.

Wikipedia mengatakan bahwa C / C ++ 'biasanya' mengimplementasikan perubahan aritmatika pada nilai yang ditandatangani.

Pada dasarnya Anda perlu menguji kompiler Anda atau tidak bergantung padanya. VS2008 bantuan saya untuk kompiler MS C ++ saat ini mengatakan bahwa kompiler mereka melakukan perubahan aritmatika.

Ronnie
sumber
141

Saat bergeser ke kiri, tidak ada perbedaan antara aritmatika dan pergeseran logis. Saat bergeser ke kanan, tipe shift tergantung pada tipe nilai yang digeser.

(Sebagai latar belakang bagi pembaca yang tidak terbiasa dengan perbedaan, pergeseran kanan "logis" dengan 1 bit menggeser semua bit ke kanan dan mengisi bit paling kiri dengan angka 0. Pergeseran "aritmatika" meninggalkan nilai asli di bit paling kiri Perbedaannya menjadi penting ketika berhadapan dengan angka negatif.)

Saat menggeser nilai yang tidak ditandatangani, >> operator di C adalah perubahan logis. Saat menggeser nilai yang ditandatangani, operator >> adalah perubahan aritmatika.

Misalnya, dengan asumsi mesin 32 bit:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);
Greg Hewgill
sumber
57
Sangat dekat, Greg. Penjelasan Anda hampir sempurna, tetapi menggeser ekspresi tipe bertanda tangan dan nilai negatif ditentukan oleh implementasi. Lihat ISO / IEC 9899: 1999 Bagian 6.5.7.
Robᵩ
12
@Rob: Sebenarnya, untuk shift kiri dan angka negatif yang ditandatangani, perilaku tidak terdefinisi.
JeremyP
5
Sebenarnya, shift kiri juga menghasilkan perilaku tidak terdefinisi untuk nilai-nilai yang ditandatangani positif jika nilai matematika yang dihasilkan (yang tidak terbatas dalam ukuran bit) tidak dapat direpresentasikan sebagai nilai positif dalam jenis yang ditandatangani. Intinya adalah bahwa Anda harus melangkah hati-hati ketika benar menggeser nilai yang ditandatangani.
Michael Burr
3
@ supercat: Saya benar-benar tidak tahu. Namun, saya tahu bahwa ada kasus yang terdokumentasi di mana kode yang memiliki perilaku tidak terdefinisi menyebabkan kompiler melakukan hal-hal yang sangat tidak intuitif (biasanya karena optimasi yang agresif - misalnya melihat driver TUN / TAP Linux lama bug null pointer: lwn.net / Artikel / 342330 ). Kecuali saya perlu sign-fill pada shift kanan (yang saya sadari adalah implementasi perilaku terdefinisi), saya biasanya mencoba untuk melakukan bit shift saya menggunakan nilai yang tidak ditandatangani, bahkan jika itu berarti menggunakan gips untuk sampai ke sana.
Michael Burr
2
@MichaelBurr: Saya tahu bahwa kompiler hypermodern menggunakan fakta bahwa perilaku yang tidak didefinisikan oleh standar C (meskipun telah didefinisikan dalam 99% implementasi ) sebagai pembenaran untuk mengubah program yang perilakunya telah sepenuhnya didefinisikan pada semua platform di mana mereka bisa diharapkan untuk berlari, ke banyak instruksi mesin yang tidak berharga tanpa perilaku yang berguna. Saya akui, meskipun (sarkasme pada) saya bingung oleh mengapa penulis kompiler telah melewatkan kemungkinan optimasi yang paling besar: hilangkan setiap bagian dari program yang, jika tercapai, akan mengakibatkan fungsi yang disarangkan ...
supercat
51

TL; DR

Pertimbangkan idan nmenjadi operan kiri dan kanan masing-masing dari operator shift; jenis i, setelah promosi bilangan bulat, menjadi T. Dengan asumsi nberada di [0, sizeof(i) * CHAR_BIT)- tidak ditentukan sebaliknya - kami memiliki kasus ini:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined  |
| Left  (<<) | unsigned |     0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |     0    | (i * 2ⁿ)                |
| Left       | signed   |    < 0    | Undefined                |

† kebanyakan kompiler mengimplementasikan ini sebagai pergeseran aritmatika
‡ tidak terdefinisi jika nilai melebihi tipe T hasil; tipe i yang dipromosikan


Bergeser

Pertama adalah perbedaan antara pergeseran logis dan aritmatika dari sudut pandang matematika, tanpa khawatir tentang ukuran tipe data. Pergeseran logis selalu mengisi bit yang dibuang dengan nol sedangkan pergeseran aritmatika mengisinya dengan nol hanya untuk shift kiri, tetapi untuk shift kanan menyalin MSB sehingga mempertahankan tanda operan (dengan asumsi komplemen dua pengkodean untuk nilai negatif).

Dengan kata lain, shift logis melihat operan yang digeser hanya sebagai aliran bit dan memindahkannya, tanpa peduli tentang tanda dari nilai yang dihasilkan. Pergeseran aritmatika melihatnya sebagai nomor (bertanda) dan mempertahankan tanda itu ketika pergantian dilakukan.

Pergeseran aritmatika kiri dari angka X oleh n sama dengan mengalikan X dengan 2 n dan dengan demikian setara dengan pergeseran kiri logis; perubahan logis juga akan memberikan hasil yang sama karena MSB akhirnya jatuh dan tidak ada yang bisa dipertahankan.

Pergeseran aritmatika kanan dari angka X oleh n sama dengan pembagian bilangan bulat X dengan 2 n HANYA jika X adalah non-negatif! Divisi integer tidak lain adalah divisi matematika dan bulat menuju 0 ( trunc ).

Untuk bilangan negatif, diwakili oleh pengkodean komplemen dua, menggeser ke kanan oleh n bit memiliki efek membaginya secara matematis dengan 2 n dan pembulatan ke arah −∞ ( lantai ); dengan demikian pergeseran kanan berbeda untuk nilai-nilai non-negatif dan negatif.

untuk X ≥ 0, X >> n = X / 2 n = trunc (X ÷ 2 n )

untuk X <0, X >> n = lantai (X ÷ 2 n )

dimana ÷adalah pembagian matematika, /adalah pembagian bilangan bulat. Mari kita lihat sebuah contoh:

37) 10 = 100101) 2

37 ÷ 2 = 18.5

37/2 = 18 (pembulatan 18,5 ke 0) = 10010) 2 [hasil pergeseran kanan aritmatika]

-37) 10 = 11011011) 2 (mempertimbangkan komplemen dua, representasi 8-bit)

-37 ÷ 2 = -18.5

-37 / 2 = -18 (pembulatan 18.5 ke 0) = 11101110) 2 [BUKAN hasil dari pergeseran kanan aritmatika]

-37 >> 1 = -19 (pembulatan 18,5 menuju −∞) = 11101101) 2 [hasil pergeseran kanan aritmatika]

Seperti yang ditunjukkan Guy Steele , perbedaan ini menyebabkan bug di lebih dari satu kompiler . Di sini nilai non-negatif (matematika) dapat dipetakan ke nilai non-negatif yang ditandatangani dan ditandatangani (C); keduanya diperlakukan sama dan menggeser-kanannya dilakukan oleh divisi integer.

Jadi logis dan aritmatika adalah setara dalam pergeseran kiri dan untuk nilai non-negatif dalam pergeseran kanan; ada pergeseran nilai-nilai negatif yang benar.

Operan dan Jenis Hasil

Standar C99 §6.5.7 :

Setiap operan harus memiliki tipe integer.

Promosi integer dilakukan pada masing-masing operan. Jenis hasilnya adalah operan kiri yang dipromosikan. Jika nilai operan kanan negatif atau lebih besar dari atau sama dengan lebar operan kiri yang dipromosikan, perilaku tidak terdefinisi.

short E1 = 1, E2 = 3;
int R = E1 << E2;

Dalam cuplikan di atas, kedua operan menjadi int(karena promosi bilangan bulat); jika E2negatif atau E2 ≥ sizeof(int) * CHAR_BIToperasi tidak terdefinisi. Ini karena menggeser lebih dari bit yang tersedia pasti akan meluap. Telah Rdinyatakan sebagai short, inthasil dari operasi shift akan secara implisit dikonversi menjadi short; konversi penyempitan, yang dapat mengarah pada perilaku yang ditentukan implementasi jika nilainya tidak dapat diwakili dalam tipe tujuan.

Shift Kiri

Hasil E1 << E2 adalah posisi bit E2 bergeser E1 kiri; bit yang dikosongkan diisi dengan nol. Jika E1 memiliki jenis yang tidak ditandatangani, nilai hasilnya adalah E1 × 2 E2 , mengurangi modulo satu lebih dari nilai maksimum yang diwakili dalam jenis hasil. Jika E1 memiliki tipe yang ditandatangani dan nilai non-negatif, dan E1 × 2 E2 dapat diwakili dalam tipe hasil, maka itu adalah nilai yang dihasilkan; jika tidak, perilaku tidak terdefinisi.

Karena shift kiri sama untuk keduanya, bit yang dikosongkan hanya diisi dengan nol. Itu kemudian menyatakan bahwa untuk kedua jenis bertanda tangan dan ditandatangani itu adalah perubahan aritmatika. Saya menafsirkannya sebagai perubahan aritmatika karena pergeseran logis tidak peduli tentang nilai yang diwakili oleh bit, itu hanya melihatnya sebagai aliran bit; tetapi standar tidak berbicara dalam hal bit, tetapi dengan mendefinisikannya dalam hal nilai yang diperoleh oleh produk E1 dengan 2 E2 .

Peringatan di sini adalah bahwa untuk jenis yang ditandatangani nilai harus non-negatif dan nilai yang dihasilkan harus dapat diwakili dalam jenis hasil. Kalau tidak, operasi tidak ditentukan. Jenis hasil akan menjadi tipe E1 setelah menerapkan promosi integral dan bukan tipe tujuan (variabel yang akan menahan hasil). Nilai yang dihasilkan secara implisit dikonversi ke tipe tujuan; jika tidak dapat diwakili dalam tipe itu, maka konversi ditentukan oleh implementasi (C99 §6.3.1.3 / 3).

Jika E1 adalah tipe bertanda tangan dengan nilai negatif maka perilaku perpindahan kiri tidak ditentukan. Ini adalah rute yang mudah menuju perilaku tidak terdefinisi yang mungkin dengan mudah diabaikan.

Shift Kanan

Hasil E1 >> E2 adalah posisi bit E2 bergeser kanan E1. Jika E1 memiliki tipe yang tidak ditandatangani atau jika E1 memiliki tipe yang ditandatangani dan nilai yang tidak negatif, nilai hasilnya adalah bagian integral dari hasil bagi dari E1 / 2 E2 . Jika E1 memiliki tipe yang ditandatangani dan nilai negatif, nilai yang dihasilkan ditentukan oleh implementasi.

Pergeseran ke kanan untuk nilai non-negatif yang ditandatangani dan ditandatangani cukup mudah; bit kosong diisi dengan nol. Untuk nilai negatif yang ditandatangani, hasil dari penggeseran kanan ditentukan oleh implementasi. Yang mengatakan, sebagian besar implementasi seperti GCC dan Visual C ++ menerapkan pergeseran kanan sebagai pergeseran aritmatika dengan mempertahankan bit tanda.

Kesimpulan

Tidak seperti Java, yang memiliki operator khusus >>>untuk pemindahan logis selain dari biasanya >>dan <<, C dan C ++ hanya memiliki pemindahan aritmatika dengan beberapa area dibiarkan tidak terdefinisi dan implementasi-didefinisikan. Alasan saya menganggap mereka sebagai aritmatika adalah karena standar kata operasi secara matematis daripada memperlakukan operan bergeser sebagai aliran bit; ini mungkin alasan mengapa hal itu membuat area-area itu tidak terdefinisi / implementasi-alih-alih hanya mendefinisikan semua kasus sebagai pergeseran logis.

legends2k
sumber
1
Jawaban bagus. Berkenaan dengan pembulatan (dalam bagian berjudul Pergeseran ) - putaran kanan mengarah -Infke angka negatif dan positif. Pembulatan ke 0 dari angka positif adalah kasus pembulatan ke arah pribadi -Inf. Saat memotong, Anda selalu menurunkan nilai tertimbang positif, karenanya Anda mengurangi hasil yang sebaliknya.
ysap
1
@ysap Ya, observasi yang bagus. Pada dasarnya, putaran menuju 0 untuk angka positif adalah kasus khusus dari putaran yang lebih umum menuju −∞; ini dapat dilihat pada tabel, di mana angka positif dan negatif yang saya catat sebagai angka bulat menuju −∞.
legends2k
17

Dalam hal jenis shift yang Anda dapatkan, yang penting adalah tipe nilai yang Anda geser. Sumber klasik bug adalah ketika Anda menggeser literal ke, katakanlah, tutup bit. Misalnya, jika Anda ingin menjatuhkan bit paling kiri dari integer yang tidak ditandatangani, maka Anda dapat mencoba ini sebagai mask Anda:

~0 >> 1

Sayangnya, ini akan membuat Anda kesulitan karena topeng akan memiliki semua bit yang ditetapkan karena nilai yang digeser (~ 0) ditandatangani, sehingga pergeseran aritmatika dilakukan. Alih-alih, Anda ingin memaksakan perubahan logis dengan secara eksplisit menyatakan nilai sebagai tidak ditandatangani, yaitu dengan melakukan sesuatu seperti ini:

~0U >> 1;
Nick
sumber
16

Berikut adalah fungsi untuk menjamin pergeseran kanan logis dan pergeseran kanan aritmatika int di C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}
John Scipione
sumber
7

Ketika Anda melakukannya - shift kiri dengan 1 Anda kalikan dengan 2 - shift kanan dengan 1 Anda bagi dengan 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)
Srikant Patnaik
sumber
Dalam x >> a dan x << a jika kondisinya adalah> 0 maka jawabannya masing-masing adalah x = x / 2 ^ a, x = x * 2 ^ a lalu Apa yang akan menjadi jawaban jika a <0?
JAVA
@unny: a tidak boleh lebih kecil dari 0. Ini adalah perilaku yang tidak terdefinisi dalam C.
Jeremy
4

Yah, saya mencarinya di wikipedia , dan mereka mengatakan ini:

Namun, C hanya memiliki satu operator shift kanan, >>. Banyak kompiler C memilih shift mana yang akan dijalankan tergantung pada tipe integer yang digeser; bilangan bulat yang sering ditandatangani digeser menggunakan pergeseran aritmatika, dan bilangan bulat yang tidak ditandatangani digeser menggunakan pergeseran logis.

Jadi sepertinya tergantung pada kompiler Anda. Juga dalam artikel itu, perhatikan bahwa shift kiri sama untuk aritmatika dan logis. Saya akan merekomendasikan melakukan tes sederhana dengan beberapa angka yang ditandatangani dan tidak ditandatangani pada kasus perbatasan (set bit tinggi tentu saja) dan melihat apa hasilnya pada kompiler Anda. Saya juga merekomendasikan untuk menghindari tergantung pada itu menjadi satu atau yang lain karena tampaknya C tidak memiliki standar, setidaknya jika itu masuk akal dan mungkin untuk menghindari ketergantungan seperti itu.

Mike Stone
sumber
Meskipun sebagian besar kompiler C dulu memiliki aritmatika bergeser ke kiri untuk nilai-nilai yang ditandatangani, perilaku yang bermanfaat seperti itu telah ditinggalkan. Filosofi kompiler sekarang tampaknya mengasumsikan bahwa kinerja shift-kiri pada variabel memberikan hak kepada kompiler untuk berasumsi bahwa variabel harus non-negatif dan dengan demikian menghilangkan kode apa pun di tempat lain yang akan diperlukan untuk perilaku yang benar jika variabel negatif. .
supercat
0

Pergeseran ke kiri <<

Ini entah bagaimana mudah dan kapan pun Anda menggunakan operator shift, itu selalu merupakan operasi yang sedikit bijaksana, jadi kami tidak dapat menggunakannya dengan operasi ganda dan float. Setiap kali kami meninggalkan shift satu nol, selalu ditambahkan ke bit paling tidak signifikan ( LSB).

Tetapi dalam shift kanan >>kita harus mengikuti satu aturan tambahan dan aturan itu disebut "sign bit copy". Arti "tanda bit copy" adalah jika bit yang paling signifikan ( MSB) diatur kemudian setelah bergeser ke kanan lagiMSB akan ditetapkan jika itu direset maka kembali diatur ulang, artinya jika nilai sebelumnya nol lalu setelah bergeser lagi, bit adalah nol jika bit sebelumnya adalah satu maka setelah shift itu adalah satu lagi. Aturan ini tidak berlaku untuk shift kiri.

Contoh paling penting pada shift kanan jika Anda menggeser angka negatif ke shift kanan, kemudian setelah beberapa pergeseran nilainya akhirnya mencapai nol dan kemudian setelah ini jika menggeser -1 ini berapa kali nilainya akan tetap sama. Silakan periksa.

asifaftab87
sumber
0

biasanya akan menggunakan shift logis pada variabel yang tidak ditandatangani dan untuk shift kiri pada variabel yang ditandatangani. Pergeseran kanan aritmatika adalah yang benar-benar penting karena akan memperpanjang variabel.

akan akan menggunakan ini ketika berlaku, karena kompiler lain mungkin melakukannya.

Cristián Romo
sumber
-1

GCC melakukannya

  1. untuk -ve -> Pergeseran Aritmatika

  2. Untuk + ve -> Shift Logis

Alok Prasad
sumber
-7

Menurut banyak orang kompiler:

  1. << adalah shift kiri aritmatika atau shift kiri bitwise.
  2. >> adalah pergeseran kanan aritmatika atau bitwise pergeseran kanan.
srinath
sumber
3
"Pergeseran kanan aritmatika" dan "pergeseran kanan bitwise" berbeda. Itulah inti pertanyaannya. Pertanyaannya adalah, "Apakah >>aritmatika atau bitwise (logis)?" Anda menjawab " >>adalah aritmatika atau bitwise." Itu tidak menjawab pertanyaan.
wchargin
Tidak, <<dan >>operator logis, bukan aritmatika
shjeff