Mengapa perilaku integer overflow unsigned didefinisikan tetapi integer overflow yang ditandatangani tidak?

210

Overflow integer yang tidak ditandai didefinisikan dengan baik oleh standar C dan C ++. Misalnya, standar C99 ( §6.2.5/9) menyatakan

Suatu perhitungan yang melibatkan operan tak bertanda tidak pernah dapat meluap, karena hasil yang tidak dapat diwakili oleh tipe integer tak bertanda yang dihasilkan dikurangi modulo angka yang satu lebih besar dari nilai terbesar yang dapat diwakili oleh jenis yang dihasilkan.

Namun, kedua standar menyatakan bahwa integer overflow yang ditandatangani adalah perilaku yang tidak terdefinisi. Sekali lagi, dari standar C99 ( §3.4.3/1)

Contoh perilaku yang tidak ditentukan adalah perilaku pada aliran bilangan bulat

Apakah ada alasan historis atau (bahkan lebih baik!) Untuk perbedaan ini?

c++ c undefined-behavior integer-overflow Anthony Vallée-Dubois
sumber
50
Mungkin karena ada lebih dari satu cara untuk mewakili bilangan bulat yang ditandatangani. Cara mana yang tidak ditentukan dalam standar, setidaknya tidak dalam C ++.
juanchopanza
Tautan yang berguna: en.wikipedia.org/wiki/Signed_number_representations
Robᵩ
7
Apa yang dikatakan juanchopanza masuk akal. Seperti yang saya pahami, standar C asli sebagian besar mengkodifikasi praktik yang ada. Jika semua implementasi pada waktu itu menyetujui apa yang harus dilakukan "overflow" yang tidak ditandatangani, itu alasan yang baik untuk menjadikannya standar. Mereka tidak setuju tentang apa yang harus dilakukan limpahan yang ditandatangani, sehingga tidak masuk dalam standar.
2
@DavidElliman Sampul yang tidak ditandatangani di samping juga mudah dideteksi ( if (a + b < a)). Overflow pada multiplikasi sulit untuk tipe yang ditandatangani dan tidak ditandatangani.
5
@ Davidvidel: Ini bukan hanya masalah apakah Anda bisa mendeteksinya, tetapi apa hasilnya. Dalam implementasi tanda + nilai MAX_INT+1 == -0,, sedangkan pada komplemen dua akanINT_MIN
David Rodríguez - dribeas

Jawaban:

163

Alasan historisnya adalah bahwa sebagian besar implementasi C (kompiler) hanya menggunakan perilaku luapan apa pun yang paling mudah diterapkan dengan representasi integer yang digunakannya. Implementasi C biasanya menggunakan representasi yang sama yang digunakan oleh CPU - jadi perilaku overflow diikuti dari representasi integer yang digunakan oleh CPU.

Dalam praktiknya, hanya representasi untuk nilai-nilai yang ditandatangani yang mungkin berbeda sesuai dengan implementasinya: komplemen satu, komplemen dua itu, magnitudo tanda. Untuk tipe unsigned, tidak ada alasan standar untuk mengizinkan variasi karena hanya ada satu representasi biner yang jelas (standar hanya mengizinkan representasi biner).

Kutipan yang relevan:

C99 6.2.6.1:3 :

Nilai yang disimpan dalam bidang bit yang tidak ditandatangani dan objek bertipe unsigned char harus diwakili menggunakan notasi biner murni.

C99 6.2.6.2 ::

Jika bit tanda adalah satu, nilainya harus dimodifikasi dengan salah satu cara berikut:

- nilai yang sesuai dengan bit tanda 0 dinegasikan ( tanda dan besarnya );

- bit tanda memiliki nilai - (2 N ) ( komplemen dua );

- bit tanda memiliki nilai - (2 N - 1) ( komplemen seseorang ).

Saat ini, semua prosesor menggunakan representasi pelengkap dua, tetapi limpahan aritmatika yang ditandatangani tetap tidak terdefinisi dan pembuat kompiler menginginkannya tetap tidak terdefinisi karena mereka menggunakan undefinedness ini untuk membantu pengoptimalan. Lihat misalnya posting blog ini oleh Ian Lance Taylor atau keluhan ini oleh Agner Fog, dan jawaban atas laporan bug-nya.

Pascal Cuoq
sumber
6
Namun, catatan penting di sini adalah bahwa tidak ada arsitektur di dunia modern yang menggunakan aritmatika bertanda tangan 2 selain yang ditandatangani. Bahwa standar bahasa masih memungkinkan untuk implementasi pada misalnya PDP-1 adalah artefak sejarah murni.
Andy Ross
9
@AndyRoss tetapi masih ada sistem (kompiler OS +, diakui dengan sejarah lama) dengan komplemen dan rilis baru pada 2013. Contoh: OS 2200.
ouah
3
@Andy Ross akan Anda anggap "tidak ada arsitektur ... menggunakan apa pun selain komplemen 2's ..." hari ini termasuk keseluruhan DSP dan prosesor yang disematkan?
chux - Reinstate Monica
11
@AndyRoss: Walaupun ada arsitektur "tidak" yang menggunakan apa pun selain komplemen 2s (untuk beberapa definisi "tidak"), pasti ada arsitektur DSP yang menggunakan aritmatika jenuh untuk bilangan bulat yang ditandatangani.
Stephen Canon
10
Aritmatika bertanda jenuh jelas sesuai dengan standar. Tentu saja instruksi pembungkus harus digunakan untuk aritmatika yang tidak ditandatangani, tetapi kompiler selalu memiliki informasi untuk mengetahui apakah aritmatika yang ditandatangani atau ditandatangani sedang dilakukan, sehingga ia dapat memilih instruksi dengan tepat.
caf
15

Selain jawaban yang baik dari Pascal (yang saya yakin adalah motivasi utama), ada kemungkinan juga bahwa beberapa prosesor menyebabkan pengecualian pada integer overflow yang ditandatangani, yang tentu saja akan menimbulkan masalah jika kompilator harus "mengatur perilaku lain" ( mis. gunakan instruksi tambahan untuk memeriksa potensi luapan dan menghitung secara berbeda dalam kasus itu).

Perlu juga dicatat bahwa "perilaku tidak terdefinisi" tidak berarti "tidak bekerja". Ini berarti bahwa implementasi diperbolehkan untuk melakukan apa pun yang disukainya dalam situasi itu. Ini termasuk melakukan "hal yang benar" serta "memanggil polisi" atau "menabrak". Kebanyakan kompiler, jika memungkinkan, akan memilih "melakukan hal yang benar", dengan anggapan bahwa itu relatif mudah untuk didefinisikan (dalam hal ini, itu). Namun, jika Anda mengalami luapan dalam perhitungan, penting untuk memahami apa yang sebenarnya dihasilkan, dan bahwa kompiler MUNGKIN melakukan sesuatu selain dari yang Anda harapkan (dan bahwa ini mungkin sangat tergantung pada versi kompiler, pengaturan optimasi, dll) .

Mats Petersson
sumber
23
Compiler tidak ingin Anda bergantung pada mereka untuk melakukan hal yang benar, dan sebagian besar dari mereka akan menunjukkan kepada Anda begitu Anda mengkompilasi int f(int x) { return x+1>x; }dengan optimasi. GCC dan ICC lakukan, dengan opsi default, mengoptimalkan di atas return 1;.
Pascal Cuoq
1
Untuk contoh program yang memberikan hasil berbeda ketika dihadapkan dengan intluapan tergantung pada tingkat optimisasi, lihat ideone.com/cki8nM Saya pikir ini menunjukkan bahwa jawaban Anda memberikan saran yang buruk.
Magnus Hoff
Saya telah sedikit mengubah bagian itu.
Mats Petersson
Jika C menyediakan sarana untuk mendeklarasikan integer "pembungkus bertanda tangani pelengkap", tidak ada platform yang dapat menjalankan C sama sekali seharusnya memiliki banyak kesulitan untuk mendukungnya, setidaknya dengan cukup efisien. Overhead tambahan akan cukup sehingga kode tidak boleh menggunakan tipe seperti itu ketika perilaku pembungkus tidak diperlukan, tetapi sebagian besar operasi pada bilangan bulat pelengkap dua identik dengan yang pada bilangan bulat tidak bertanda, kecuali untuk perbandingan dan promosi.
supercat
1
Nilai negatif perlu ada dan "berfungsi" agar kompiler bekerja dengan benar, Tentu saja sangat mungkin untuk mengatasi kekurangan nilai yang ditandatangani dalam prosesor, dan menggunakan nilai yang tidak ditandatangani, baik sebagai pelengkap atau pelengkap dua, yang mana yang paling banyak membuat akal berdasarkan apa set instruksi. Ini biasanya akan jauh lebih lambat untuk melakukan ini daripada memiliki dukungan perangkat keras untuk itu, tetapi tidak berbeda dari prosesor yang tidak mendukung floating point dalam perangkat keras, atau serupa - itu hanya menambah banyak kode tambahan.
Mats Petersson
10

Pertama-tama, harap dicatat bahwa C11 3.4.3, seperti semua contoh dan catatan kaki, bukan teks normatif dan karenanya tidak relevan untuk dikutip!

Teks yang relevan yang menyatakan bahwa overflow bilangan bulat dan float adalah perilaku yang tidak didefinisikan adalah ini:

C11 6.5 / 5

Jika kondisi luar biasa terjadi selama evaluasi ekspresi (yaitu, jika hasilnya tidak didefinisikan secara matematis atau tidak dalam kisaran nilai yang dapat diwakili untuk jenisnya), perilaku tersebut tidak terdefinisi.

Klarifikasi mengenai perilaku tipe bilangan bulat yang tidak ditandatangani secara spesifik dapat ditemukan di sini:

C11 6.2.5 / 9

Kisaran nilai nonnegatif dari tipe integer yang ditandatangani adalah subrange dari tipe integer yang tidak ditandatangani, dan representasi dari nilai yang sama di setiap tipe adalah sama. Suatu perhitungan yang melibatkan operan tak bertanda tidak pernah bisa meluap, karena hasil yang tidak dapat diwakili oleh tipe integer tak bertanda yang dihasilkan berkurang modulo angka yang satu lebih besar dari nilai terbesar yang dapat diwakili oleh jenis yang dihasilkan.

Ini membuat tipe integer yang tidak ditandai sebagai kasus khusus.

Perhatikan juga bahwa ada pengecualian jika jenis apa pun dikonversi ke jenis yang ditandatangani dan nilai lama tidak lagi dapat diwakili. Perilaku ini kemudian hanya implementasi-didefinisikan, meskipun sinyal dapat dinaikkan.

C11 6.3.1.3

6.3.1.3 Bilangan bulat yang ditandatangani dan tidak ditandatangani

Ketika nilai dengan tipe integer dikonversi ke tipe integer lain selain _Bool, jika nilainya dapat diwakili oleh tipe baru, itu tidak berubah.

Jika tidak, jika tipe baru tidak ditandatangani, nilainya dikonversi dengan berulang kali menambahkan atau mengurangi satu lebih dari nilai maksimum yang dapat direpresentasikan dalam tipe baru hingga nilainya berada dalam kisaran tipe baru.

Jika tidak, tipe baru ditandatangani dan nilainya tidak dapat diwakili di dalamnya; baik hasilnya adalah implementasi yang ditentukan atau sinyal yang ditentukan oleh implementasi dinaikkan.

Lundin
sumber
6

Selain masalah lain yang disebutkan, memiliki bungkus matematika yang tidak ditandatangani membuat tipe integer yang tidak ditandatangani berperilaku sebagai kelompok aljabar abstrak (artinya, antara lain, untuk setiap pasangan nilai Xdan Y, akan ada beberapa nilai Zlain yang X+Zakan, jika dilemparkan dengan benar , sama ). Jika nilai yang tidak ditandatangani hanyalah tipe lokasi penyimpanan dan bukan tipe ekspresi menengah (mis. Jika tidak ada padanan unsigned dari tipe integer terbesar, dan operasi aritmatika pada tipe unsigned berperilaku seolah-olah mereka pertama kali mengonversikannya ke tipe yang ditandatangani lebih besar, maka ada tidak akan sebanyak kebutuhan untuk perilaku pembungkus yang ditentukan, tetapi sulit untuk melakukan perhitungan dalam jenis yang tidak memiliki mis invers tambahan.Y dan Y-Zakan, jika dilemparkan dengan benar, samaX

Ini membantu dalam situasi di mana perilaku wrap-around sebenarnya berguna - misalnya dengan nomor urut TCP atau algoritma tertentu, seperti perhitungan hash. Mungkin juga membantu dalam situasi di mana perlu untuk mendeteksi luapan, karena melakukan perhitungan dan memeriksa apakah meluap sering lebih mudah daripada memeriksa di muka apakah akan meluap, terutama jika perhitungan melibatkan tipe bilangan bulat terbesar yang tersedia.

supercat
sumber
Saya tidak cukup mengikuti - mengapa membantu memiliki invers terbalik? Saya benar-benar tidak bisa memikirkan situasi di mana perilaku meluap sebenarnya berguna ...
sleske
@sleske: Menggunakan desimal untuk keterbacaan manusia, jika meteran energi membaca 0003 dan pembacaan sebelumnya adalah 9995, apakah itu berarti bahwa -9992 unit energi digunakan, atau bahwa 0008 unit energi digunakan? Memiliki hasil 0003-9995 0008 membuatnya mudah untuk menghitung hasil yang terakhir. Setelah itu menghasilkan -9992 akan membuatnya sedikit lebih canggung. Namun, karena tidak dapat melakukannya, akan diperlukan untuk membandingkan 0003 hingga 9995, perhatikan bahwa ini lebih sedikit, lakukan pengurangan terbalik, kurangi hasil itu dari 9999, dan tambahkan 1.
supercat
@sleske: Ini juga sangat berguna bagi manusia dan penyusun untuk dapat menerapkan hukum aritmatika asosiatif, distributif, dan komutatif untuk menulis ulang ekspresi dan menyederhanakannya; misalnya, jika ekspresi a+b-cdihitung dalam satu loop, tetapi bdan ckonstan dalam loop itu, mungkin akan membantu untuk memindahkan perhitungan di (b-c)luar loop, tetapi melakukan hal itu akan membutuhkan di antara hal-hal lain yang (b-c)menghasilkan nilai yang, ketika ditambahkan ke a, akan menghasilkan a+b-c, yang pada gilirannya mengharuskan yang cmemiliki aditif terbalik.
supercat
: Terima kasih atas penjelasannya. Jika saya memahaminya dengan benar, semua contoh Anda mengasumsikan bahwa Anda sebenarnya ingin menangani overflow. Dalam kebanyakan kasus yang saya temui, overflow tidak diinginkan, dan Anda ingin mencegahnya, karena hasil perhitungan dengan overflow tidak berguna. Misalnya, untuk pengukur energi Anda mungkin ingin menggunakan jenis yang tidak pernah terjadi.
sleske
1
... sedemikian rupa sehingga (a+b)-csama dengan a+(b-c)apakah nilai aritmatika b-cdapat diwakili dalam tipe, substitusi akan valid terlepas dari rentang nilai yang dimungkinkan untuk (b-c).
supercat
1

Mungkin alasan lain mengapa aritmatika unsigned didefinisikan adalah karena bilangan unsigned membentuk bilangan bulat modulo 2 ^ n, di mana n adalah lebar bilangan unsigned. Angka yang tidak ditandai hanyalah bilangan bulat yang direpresentasikan menggunakan digit biner alih-alih digit desimal. Melakukan operasi standar dalam sistem modulus dipahami dengan baik.

Kutipan OP mengacu pada fakta ini, tetapi juga menyoroti fakta bahwa hanya ada satu, cara yang jelas, logis untuk mewakili bilangan bulat tidak bertanda dalam biner. Sebaliknya, angka yang ditandatangani paling sering direpresentasikan menggunakan komplemen dua tetapi pilihan lain dimungkinkan seperti yang dijelaskan dalam standar (bagian 6.2.6.2).

Representasi komplemen dua memungkinkan operasi tertentu untuk lebih masuk akal dalam format biner. Misalnya, penambahan bilangan negatif sama dengan bilangan positif (perkirakan dalam kondisi luapan). Beberapa operasi di level mesin bisa sama untuk nomor yang ditandatangani dan tidak ditandatangani. Namun, ketika menginterpretasikan hasil dari operasi tersebut, beberapa kasus tidak masuk akal - luapan positif dan negatif. Selain itu, hasil melimpah berbeda tergantung pada representasi yang ditandatangani yang mendasarinya.

yth
sumber
Agar struktur menjadi bidang, setiap elemen struktur selain identitas aditif harus memiliki inversi multiplikatif. Struktur bilangan bulat congruent mod N akan menjadi bidang hanya ketika N adalah satu atau prima [bidang degnerasi ketika N == 1]. Apakah ada sesuatu yang Anda rasa saya lewatkan dalam jawaban saya?
supercat
Kamu benar. Saya jadi bingung oleh moduli kekuatan utama. Respons asli diedit.
yth
Ekstra membingungkan di sini adalah bahwa ada adalah bidang ketertiban 2 ^ n, itu hanya tidak cincin-isomorfik ke integer modulo 2 ^ n.
Kevin Ventullo
Dan, 2 ^ 31-1 adalah Perdana Mersenne (tapi 2 ^ 63-1 bukan perdana). Dengan demikian, ide asli saya hancur. Juga, ukuran bilangan bulat berbeda pada hari itu. Jadi, ide saya adalah revisionis.
yth
Fakta bahwa bilangan bulat bertanda tangan membentuk sebuah cincin (bukan bidang), mengambil bagian pesanan rendah juga menghasilkan cincin, dan melakukan operasi pada seluruh nilai dan kemudian memotong akan berperilaku setara dengan melakukan operasi pada bagian yang lebih rendah, adalah IMHO pertimbangan hampir pasti.
supercat