Apakah pengurangan integer tidak bertanda tangan didefinisikan sebagai perilaku?

100

Saya telah menemukan kode dari seseorang yang tampaknya percaya ada masalah mengurangi bilangan bulat unsigned dari bilangan bulat lain dari jenis yang sama ketika hasilnya akan negatif. Jadi kode seperti ini tidak akan benar meskipun kebetulan berfungsi pada sebagian besar arsitektur.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Ini adalah satu-satunya kutipan relevan yang samar-samar dari standar C yang dapat saya temukan.

Perhitungan yang melibatkan operand unsigned tidak akan pernah bisa overflow, karena hasil yang tidak dapat diwakili oleh jenis unsigned integer yang dihasilkan dikurangi modulo bilangan yang satu lebih besar dari nilai terbesar yang dapat diwakili oleh jenis yang dihasilkan.

Saya kira orang bisa mengambil kutipan itu berarti bahwa ketika operan kanan lebih besar operasi disesuaikan agar bermakna dalam konteks nomor terpotong modulo.

yaitu

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

sebagai kebalikan dari penggunaan semantik bertanda tangan yang bergantung pada implementasi:

0x0000 - 0x0001 == (unsigned) (0 + -1) == (0xFFFF tetapi juga 0xFFFE atau 0x8001)

Manakah atau interpretasi apa yang benar? Apakah itu didefinisikan sama sekali?

c standards unsigned integer-arithmetic LihO
sumber
3
Pilihan kata dalam standar sangat disayangkan. Bahwa "tidak pernah dapat meluap" berarti bahwa ini bukan situasi kesalahan. Menggunakan terminologi dalam standar, alih-alih meluap-luap nilai "wraps".
danorton

Jawaban:

107

Hasil pengurangan yang menghasilkan bilangan negatif dalam tipe unsigned didefinisikan dengan baik:

  1. [...] Perhitungan yang melibatkan operand unsigned tidak akan pernah dapat meluap, karena hasil yang tidak dapat diwakili oleh jenis integer unsigned yang dihasilkan dikurangi modulo dengan bilangan yang satu lebih besar dari nilai terbesar yang dapat diwakili oleh jenis yang dihasilkan. (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Seperti yang Anda lihat, (unsigned)0 - (unsigned)1sama dengan -1 modulo UINT_MAX + 1, atau dengan kata lain, UINT_MAX.

Perhatikan bahwa meskipun dikatakan "Perhitungan yang melibatkan operan unsigned tidak akan pernah bisa meluap", yang mungkin membuat Anda percaya bahwa ini hanya berlaku untuk melebihi batas atas, ini disajikan sebagai motivasi untuk bagian pengikatan sebenarnya dari kalimat: "a hasil yang tidak dapat diwakili oleh jenis bilangan bulat unsigned yang dihasilkan dikurangi modulo angka yang lebih besar dari nilai terbesar yang dapat diwakili oleh jenis yang dihasilkan. " Frasa ini tidak terbatas pada luapan batas atas tipe, dan berlaku sama untuk nilai yang terlalu rendah untuk diwakili.

bdonlan.dll
sumber
2
Terima kasih! Sekarang saya melihat interpretasi yang saya lewatkan. Saya pikir mereka bisa memilih kata-kata yang lebih jelas.
4
Saya merasa jauh lebih baik sekarang, mengetahui bahwa jika ada penambahan unsigned berguling ke nol dan menyebabkan kekacauan, itu karena uintselalu dimaksudkan untuk mewakili cincin matematika dari bilangan bulat 0melalui UINT_MAX, dengan operasi modulo penjumlahan dan perkalian UINT_MAX+1, dan bukan karena dari luapan. Namun, hal itu menimbulkan pertanyaan mengapa, jika cincin adalah tipe data fundamental, bahasa tersebut tidak menawarkan dukungan yang lebih umum untuk cincin dengan ukuran lain.
Theodore Murdock
2
@TheodoreMurdock Saya rasa jawaban atas pertanyaan itu sederhana. Sejauh yang saya tahu, fakta bahwa itu cincin adalah konsekuensi, bukan penyebab. Persyaratan sebenarnya adalah bahwa tipe unsigned harus memiliki semua bitnya yang berpartisipasi dalam representasi nilai. Perilaku seperti cincin mengalir secara alami dari situ. Jika Anda menginginkan perilaku seperti itu dari tipe lain, lakukan aritmatika diikuti dengan menerapkan modulus yang diperlukan; yang menggunakan operator dasar.
underscore_d
@underscore_d Tentu saja ... jelas mengapa mereka membuat keputusan desain. Sangat lucu bahwa mereka menulis spesifikasi secara kasar sebagai "tidak ada aritmatika over / underflow karena tipe datanya dispesifikasi sebagai cincin", seolah-olah pilihan desain ini berarti bahwa pemrogram tidak harus hati-hati menghindari over- and under -flow atau program mereka gagal secara spektakuler.
Theodore Murdock
120

Saat Anda bekerja dengan tipe unsigned , aritmatika modular (juga dikenal sebagai perilaku "membungkus" ) berlangsung. Untuk memahami aritmatika modular ini , lihat saja jam-jam berikut:

masukkan deskripsi gambar di sini

9 + 4 = 1 ( 13 mod 12 ), jadi untuk arah lainnya adalah: 1 - 4 = 9 ( -3 mod 12 ). Prinsip yang sama diterapkan saat bekerja dengan tipe unsigned. Jika jenis hasil adalah unsigned, maka aritmatika modular berlangsung.

Sekarang lihat operasi berikut yang menyimpan hasil sebagai unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Ketika Anda ingin memastikan bahwa hasilnya adalah signed, simpan ke dalam signedvariabel atau cast ke signed. Jika Anda ingin mendapatkan perbedaan antara angka dan memastikan bahwa aritmatika modular tidak akan diterapkan, Anda harus mempertimbangkan untuk menggunakan abs()fungsi yang ditentukan dalam stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Berhati-hatilah, terutama saat menulis kondisi, karena:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

tapi

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...
LihO
sumber
4
Bagus dengan jamnya, meskipun bukti akan membuat ini menjadi jawaban yang benar. Premis pertanyaan tersebut sudah mencakup pernyataan bahwa semua ini mungkin benar.
Balapan Ringan di Orbit
5
@LightnessRacesinOrbit: Terima kasih. Saya menulisnya karena saya pikir seseorang mungkin menganggapnya sangat membantu. Saya setuju, itu bukan jawaban yang lengkap.
LihO
4
Antreannya int d = abs(five - seven);tidak bagus. Pertama five - sevendihitung: promosi meninggalkan jenis operan sebagai unsigned int, hasilnya dihitung modulo (UINT_MAX+1), dan dievaluasi ke UINT_MAX-1. Maka nilai ini adalah parameter aktual untuk abs, yaitu berita buruk. abs(int)menyebabkan perilaku tidak terdefinisi meneruskan argumen, karena tidak dalam jangkauan, dan abs(long long)mungkin dapat menahan nilai, tetapi perilaku tak terdefinisi terjadi ketika nilai yang dikembalikan dipaksa intuntuk menginisialisasi d.
Ben Voigt
1
@LihO: Satu-satunya operator di C ++ yang peka konteks dan bertindak berbeda bergantung pada bagaimana hasilnya digunakan adalah operator konversi khusus operator T(). Penambahan dua ekspresi yang kita diskusikan dilakukan dalam tipe unsigned int, berdasarkan tipe operan. Hasil penjumlahan adalah unsigned int. Kemudian hasil tersebut secara implisit dikonversi ke jenis yang diperlukan dalam konteks, sebuah konversi yang gagal karena nilainya tidak dapat direpresentasikan dalam jenis baru.
Ben Voigt
1
@ LihO: Mungkin membantu untuk memikirkan double x = 2/3;vsdouble y = 2.0/3;
Ben Voigt
5

Nah, interpretasi pertama benar. Namun, alasan Anda tentang "semantik bertanda tangan" dalam konteks ini salah.

Sekali lagi, interpretasi pertama Anda benar. Aritmatika unsigned mengikuti aturan aritmatika modulo, yang berarti 0x0000 - 0x0001mengevaluasi ke 0xFFFFuntuk jenis unsigned 32-bit.

Namun, interpretasi kedua (yang didasarkan pada "semantik bertanda tangan") juga diperlukan untuk menghasilkan hasil yang sama. Yaitu bahkan jika Anda mengevaluasi 0 - 1dalam domain tipe bertanda tangan dan mendapatkan -1sebagai hasil perantara, ini -1masih diperlukan untuk menghasilkan 0xFFFFketika nanti diubah ke tipe tak bertanda. Bahkan jika beberapa platform menggunakan representasi eksotis untuk bilangan bulat bertanda (komplemen 1, besaran bertanda), platform ini masih diharuskan untuk menerapkan aturan aritmatika modulo saat mengonversi nilai bilangan bulat bertanda ke yang tidak bertanda.

Misalnya evaluasi ini

signed int a = 0, b = 1;
unsigned int c = a - b;

masih dijamin untuk menghasilkan UINT_MAXdi c, bahkan jika platform ini menggunakan representasi eksotis untuk bilangan bulat ditandatangani.

Semut
sumber
4
Saya pikir yang Anda maksud adalah tipe unsigned 16 bit, bukan 32 bit.
xioxox
4

Dengan nomor unsigned dari jenis unsigned intatau lebih besar, dengan tidak adanya konversi jenis, a-bdidefinisikan sebagai menghasilkan nomor unsigned yang, bila ditambahkan b, akan menghasilkan a. Konversi bilangan negatif menjadi unsigned didefinisikan sebagai menghasilkan bilangan yang, jika ditambahkan ke bilangan asli yang dibalik tanda, akan menghasilkan nol (jadi mengubah -5 menjadi unsigned akan menghasilkan nilai yang, jika ditambahkan ke 5, akan menghasilkan nol) .

Perhatikan bahwa angka unsigned lebih kecil dari yang unsigned intdapat dipromosikan menjadi tipe intsebelum pengurangan, perilaku a-bakan tergantung pada ukuran int.

supercat
sumber