Mengapa nomor yang tidak ditandai diterapkan?

Saya tidak tahu mengapa sistem mikroprosesor menerapkan angka yang tidak ditandatangani. Saya kira biayanya hanya dua kali lipat jumlah cabang kondisional, karena lebih besar dari, kurang dari, dll

pertanyaan saya sebagian adalah mengapa mereka harus ada dalam set instruksi yang bertentangan didukung oleh kompiler?

Angka yang tidak ditandai adalah salah satu interpretasi dari urutan bit. Ini juga merupakan interpretasi yang paling sederhana, dan paling banyak digunakan secara internal ke CPU karena alamat, dan kode op hanyalah bit. Pengalamatan memori / tumpukan dan aritmatika adalah dasar dari mikroprosesor, baik, pemrosesan. Pindah ke atas piramida abstraksi, interpretasi lain yang sering bit adalah sebagai karakter (ASCII, Unicode, EBCDIC). Lalu ada interpretasi lain seperti IEEE Floating point, RGBA untuk grafik, dan sebagainya. Tidak satu pun dari ini adalah angka yang ditandatangani sederhana (IEEE FP tidak sederhana, dan aritmatika menggunakan itu sangat rumit).

Juga, dengan aritmatika yang tidak ditandatangani, itu sangat mudah (jika tidak paling efisien) untuk mengimplementasikan yang lain. Kebalikannya tidak benar.

Sebagian besar biaya perangkat keras untuk operasi perbandingan adalah pengurangan. Output dari pengurangan yang digunakan oleh perbandingan pada dasarnya adalah tiga bit status:

• apakah semua bit nol (yaitu kondisi yang sama),
• tanda bit hasilnya
• bit carry dari pengurangan (yaitu bit orde tinggi 33 pada komputer 32-bit)

Dengan kombinasi yang tepat dari pengujian tiga bit ini setelah operasi pengurangan, kita dapat menentukan semua operasi relasional yang ditandatangani, serta semua operasi relasional yang tidak ditandatangani (bit-bit ini juga bagaimana meluapnya terdeteksi, ditandatangani vs tidak ditandatangani). Perangkat keras ALU dasar yang sama dapat digunakan bersama untuk mengimplementasikan semua perbandingan ini (belum termasuk instruksi pengurangan), hingga pemeriksaan akhir dari ketiga bit status tersebut, yang berbeda sesuai dengan perbandingan relasional yang diinginkan. Jadi, tidak banyak perangkat keras tambahan.

Satu-satunya biaya nyata adalah kebutuhan untuk pengkodean mode perbandingan tambahan dalam arsitektur set instruksi, yang mungkin sedikit mengurangi kepadatan instruksi. Namun, sangat normal bahwa perangkat keras memiliki banyak instruksi yang tidak digunakan oleh bahasa tertentu.

Karena, jika Anda perlu menghitung sesuatu yang selalu >= 0 , Anda tidak perlu memotong ruang hitung Anda menjadi setengah menggunakan bilangan bulat yang ditandatangani.

Pertimbangkan INT PK yang ditambahkan otomatis yang mungkin Anda letakkan di tabel basis data Anda. Jika Anda menggunakan bilangan bulat yang ditandatangani di sana, tabel Anda menyimpan SETENGAH sebanyak mungkin untuk ukuran bidang yang sama tanpa manfaat.

Atau oktet warna RGBa. Kami tidak ingin dengan canggung mulai menghitung konsep bilangan positif alami ini pada bilangan negatif. Nomor yang ditandatangani akan mematahkan model mental atau membagi dua ruang kita. Integer yang tidak ditandatangani tidak hanya cocok dengan konsep, tetapi juga memberikan resolusi dua kali lipat.

Dari perspektif perangkat keras, bilangan bulat tak bertanda sederhana. Mereka mungkin struktur bit paling mudah untuk melakukan matematika. Dan, tidak diragukan lagi, kita dapat menyederhanakan perangkat keras dengan mensimulasikan tipe integer (atau bahkan floating point!) Dalam kompiler. Jadi, mengapa bilangan bulat ditandatangani dan ditandatangani diimplementasikan dalam perangkat keras?

Ya ... kinerja!

Lebih efisien untuk mengimplementasikan bilangan bulat yang ditandatangani di perangkat keras daripada di perangkat lunak. Perangkat keras dapat diinstruksikan untuk melakukan matematika pada kedua jenis integer dalam satu instruksi. Dan itu sangat bagus , karena perangkat keras menghancurkan bit secara bersamaan kurang lebih secara paralel. Jika Anda mencoba mensimulasikannya dalam perangkat lunak, tipe integer yang Anda pilih untuk "disimulasikan" tidak diragukan lagi akan membutuhkan banyak instruksi dan terasa lebih lambat.

Pertanyaan Anda terdiri dari dua bagian:

1. Apa tujuan dari bilangan bulat yang tidak ditandatangani?

2. Apakah bilangan bulat yang tidak ditandatangani bernilai masalah?

1. Apa tujuan dari bilangan bulat yang tidak ditandatangani?

Angka yang tidak ditandai, cukup sederhana, mewakili kelas jumlah yang nilai negatifnya tidak ada artinya. Tentu, Anda mungkin mengatakan bahwa jawaban untuk pertanyaan "berapa banyak apel yang saya miliki?" mungkin angka negatif jika Anda berutang beberapa apel kepada seseorang, tetapi bagaimana dengan pertanyaan "berapa banyak memori yang saya miliki?" --Anda tidak dapat memiliki jumlah memori negatif. Jadi, bilangan bulat tak bertanda sangat cocok untuk mewakili jumlah seperti itu, dan mereka memiliki manfaat karena mampu mewakili dua kali kisaran nilai positif dari bilangan bulat yang ditandatangani. Misalnya, nilai maksimum yang dapat Anda wakili dengan integer bertanda 16-bit adalah 32767, sedangkan dengan integer 16-bit unsigned adalah 65535.

2. Apakah bilangan bulat yang tidak ditandatangani bernilai masalah?

Bilangan bulat yang tidak ditandatangani tidak benar-benar mewakili masalah, jadi, ya, mereka sepadan. Anda lihat, mereka tidak memerlukan set "algoritma" tambahan; sirkuit yang diperlukan untuk mengimplementasikannya adalah himpunan bagian dari sirkuit yang diperlukan untuk mengimplementasikan bilangan bulat yang ditandatangani.

CPU tidak memiliki satu pengali untuk bilangan bulat yang ditandatangani dan pengali yang berbeda untuk yang tidak ditandatangani; ia hanya memiliki satu pengali, yang bekerja dengan cara yang sedikit berbeda tergantung pada sifat operasi. Mendukung multiplikasi yang ditandatangani memerlukan sirkuit yang sedikit lebih banyak daripada yang tidak ditandatangani, tetapi karena perlu didukung pula, multiplikasi yang tidak bertanda datang secara praktis gratis, itu termasuk dalam paket.

Adapun penambahan dan pengurangan, tidak ada perbedaan dalam sirkuit sama sekali. Jika Anda membaca tentang representasi komplemen bilangan pelengkap yang disebut dua, Anda akan mendapati bahwa bilangan tersebut dirancang dengan sangat cerdik sehingga operasi ini dapat dilakukan dengan cara yang persis sama, terlepas dari sifat bilangan bulat.

Perbandingan juga bekerja dengan cara yang sama, karena tidak lain adalah kurangi-dan-buang-hasilnya, satu-satunya perbedaan adalah dalam instruksi cabang bersyarat (lompatan), yang bekerja dengan melihat berbagai flag CPU yang ditetapkan oleh instruksi sebelumnya (perbandingan). Dalam jawaban ini: /programming//a/9617990/773113 Anda dapat menemukan penjelasan tentang bagaimana mereka bekerja pada arsitektur Intel x86. Apa yang terjadi adalah bahwa penunjukan instruksi lompat bersyarat sebagai ditandatangani atau tidak ditandatangani tergantung pada bendera mana yang diperiksa.

Mikroprosesor secara inheren tidak ditandatangani. Nomor yang ditandatangani adalah hal yang diterapkan, bukan sebaliknya.

Komputer dapat dan bekerja dengan baik tanpa angka yang ditandatangani, tetapi kita, manusia yang membutuhkan angka negatif, oleh karenanya signness diciptakan.

Karena mereka memiliki satu bit lagi yang mudah tersedia untuk penyimpanan, dan Anda tidak perlu khawatir tentang angka negatif. Tidak ada yang lebih dari itu.

Sekarang jika Anda memerlukan contoh di mana Anda akan membutuhkan bit tambahan ini, ada banyak yang bisa ditemukan jika Anda melihatnya.

Contoh favorit saya berasal dari bitboard di mesin Catur. Ada 64 kotak pada papan catur, sehingga unsigned longmenyediakan penyimpanan yang sempurna untuk berbagai algoritma yang berputar di sekitar pergerakan generasi. Mempertimbangkan fakta bahwa Anda perlu operasi biner (serta operasi shift !!), mudah untuk melihat mengapa lebih mudah untuk tidak perlu khawatir tentang hal-hal khusus apa yang terjadi jika MSB diatur. Itu bisa dilakukan dengan ditandatangani lama, tetapi jauh lebih mudah untuk menggunakan yang tidak ditandatangani.

Memiliki latar belakang matematika murni, ini sedikit lebih matematis bagi siapa pun yang tertarik.

Jika kita mulai dengan bilangan bulat 8bit yang ditandatangani dan tidak ditandatangani, yang kita miliki pada dasarnya adalah bilangan bulat modulo 256, sejauh menyangkut penambahan dan perkalian, asalkan komplemen 2's digunakan untuk mewakili bilangan bulat negatif (dan ini adalah bagaimana setiap prosesor modern melakukannya) .

Di mana ada perbedaan di dua tempat: satu adalah operasi perbandingan. Dalam arti tertentu, bilangan bulat modulo 256 paling baik dianggap sebagai lingkaran angka (seperti bilangan bulat modulo 12 lakukan pada clockface analog kuno). Untuk membuat perbandingan numerik (adalah x <y) bermakna, kita perlu memutuskan angka mana yang lebih sedikit dari yang lain. Dari sudut pandang ahli matematika, kami ingin menanamkan bilangan bulat modulo 256 ke dalam himpunan semua bilangan bulat entah bagaimana. Memetakan bilangan bulat 8bit yang representasi binernya nol untuk bilangan bulat 0 adalah hal yang jelas untuk dilakukan. Kita kemudian dapat melanjutkan untuk memetakan orang lain sehingga '0 +1' (hasil dari nolkan register, katakanlah kapak, dan kenaikan itu satu, melalui 'inc kapak') pergi ke bilangan bulat 1, dan seterusnya. Kita dapat melakukan hal yang sama dengan -1, misalnya memetakan '0-1' ke integer -1, dan '0-1-1' ke bilangan bulat -2. Kami harus memastikan bahwa penyematan ini adalah fungsi, jadi tidak dapat memetakan bilangan bulat 8bit tunggal ke dua bilangan bulat. Dengan demikian, ini berarti bahwa jika kita memetakan semua angka ke dalam himpunan bilangan bulat, 0 akan ada di sana, bersama dengan beberapa bilangan bulat kurang dari 0 dan beberapa lebih dari 0. Pada dasarnya ada 255 cara untuk melakukan ini dengan bilangan bulat 8bit (menurut hingga minimum yang Anda inginkan, dari 0 hingga -255). Kemudian Anda dapat mendefinisikan 'x <y' dalam hal '0 <y - x'.

Ada dua kasus penggunaan umum, di mana dukungan perangkat keras masuk akal: satu dengan semua bilangan nol bukan yang lebih besar dari 0, dan satu dengan sekitar 50/50 membagi sekitar 0. Semua kemungkinan lain mudah ditiru dengan menerjemahkan angka melalui penambahan tambahan. dan sebelum operasi, dan kebutuhan untuk ini sangat langka daripada saya tidak bisa memikirkan contoh eksplisit dalam perangkat lunak modern (karena Anda hanya dapat bekerja dengan mantissa yang lebih besar, katakanlah 16 bit).

Masalah lainnya adalah memetakan bilangan bulat 8bit ke dalam ruang bilangan bulat 16bit. Apakah -1 menuju ke -1? Ini yang Anda inginkan jika 0xFF dimaksudkan untuk mewakili -1. Dalam hal ini, perpanjangan tanda adalah hal yang masuk akal untuk dilakukan, sehingga 0xFF masuk ke 0xFFFF. Di sisi lain, jika 0xFF dimaksudkan untuk mewakili 255, maka Anda ingin memetakannya ke 255, maka ke 0x00FF, bukan 0xFFFF.

Ini adalah perbedaan antara operasi 'shift' dan 'shift aritmatika' juga.

Pada akhirnya, bagaimanapun, itu datang ke fakta bahwa int dalam perangkat lunak bukan bilangan bulat, tetapi representasi dalam biner, dan hanya beberapa yang dapat diwakili. Saat mendesain perangkat keras, harus dibuat pilihan untuk melakukan apa secara native pada perangkat keras. Karena dengan komplemen 2's, operasi penjumlahan dan multiplikasi identik, masuk akal untuk mewakili bilangan bulat negatif dengan cara ini. Maka itu hanya masalah operasi yang bergantung pada bilangan bulat mana representasi biner Anda dimaksudkan untuk diwakili.

Mari kita periksa biaya implementasi untuk menambahkan bilangan bulat yang tidak ditandatangani ke desain CPU dengan bilangan bulat yang sudah ditandatangani.

CPU tipikal memerlukan instruksi aritmatika berikut:

• ADD (yang menambahkan dua nilai dan menetapkan bendera jika operasi meluap)
• SUB (yang mengurangi satu nilai dari yang lain dan menetapkan berbagai flag - kita akan membahas ini di bawah)
• CMP (yang pada dasarnya adalah 'SUB dan buang hasilnya, hanya simpan benderanya')
• LSH (shift kiri, tetapkan flag pada overflow)
• RSH (shift kanan, tetapkan bendera jika 1 digeser keluar)
• Varian dari semua instruksi di atas yang menangani pengangkutan / peminjaman dari flag, sehingga memungkinkan Anda untuk mengaitkan instruksi bersama-sama dengan nyaman untuk beroperasi pada tipe yang lebih besar daripada register CPU.
• MUL (multiply, set flags, dll - tidak tersedia secara universal)
• DIV (bagi, set bendera, dll - banyak arsitektur CPU kekurangan ini)
• Pindah dari tipe integer yang lebih kecil (mis. 16-bit) ke tipe yang lebih besar (mis. 32-bit). Untuk bilangan bulat yang ditandatangani, ini biasanya disebut MOVSX (bergerak dengan tanda perpanjangan).

Itu juga membutuhkan instruksi logis:

• Cabang di nol
• Cabang lebih besar
• Cabang kurang
• Cabang meluap
• Versi yang dinegasikan dari semua hal di atas

Untuk melakukan cabang di atas pada perbandingan integer yang ditandatangani, cara termudah adalah dengan meminta instruksi SUB mengatur flag berikut:

• Nol. Setel jika pengurangan menghasilkan nilai nol.
• Meluap. Setel jika pengurangan meminjam nilai dari bit paling signifikan.
• Tanda. Setel ke bit tanda hasil.

Kemudian cabang aritmatika diimplementasikan sebagai berikut:

• Cabang pada nol: jika nol bendera diatur
• Cabang pada kurang: jika bendera tanda berbeda dengan bendera melimpah
• Cabang pada lebih besar: jika bendera tanda sama dengan bendera melimpah, dan bendera nol jelas.

Negasi ini harus mengikuti jelas dari bagaimana mereka diterapkan.

Jadi desain yang ada sudah mengimplementasikan semua ini untuk bilangan bulat yang ditandatangani. Sekarang mari kita pertimbangkan apa yang perlu kita lakukan untuk menambahkan bilangan bulat yang tidak ditandai:

• ADD - implementasi ADD identik.
• SUB - kita perlu menambahkan bendera tambahan: bendera carry ditetapkan ketika nilai dipinjam dari luar bit paling signifikan dari register.
• CMP - tidak berubah
• LSH - tidak berubah
• RSH - perubahan yang tepat untuk nilai yang ditandatangani mempertahankan nilai bit yang paling signifikan. Untuk nilai yang tidak ditandatangani, kita harus mengaturnya ke nol.
• MUL - jika ukuran output Anda sama dengan input, tidak diperlukan penanganan khusus (x86 memang memiliki penanganan khusus, tetapi hanya karena memiliki keluaran menjadi pasangan register, tetapi perhatikan bahwa fasilitas ini sebenarnya sangat jarang digunakan, sehingga akan menjadi kandidat yang lebih jelas untuk keluar dari prosesor daripada tipe yang tidak ditandai)
• DIV - tidak diperlukan perubahan
• Pindah dari tipe yang lebih kecil ke tipe yang lebih besar - perlu menambahkan MOVZX, bergerak dengan zero extended. Perhatikan bahwa MOVZX sangat sederhana untuk diimplementasikan.
• Cabang pada nol - tidak berubah
• Cabang kurang - melompat ketika membawa set bendera.
• Cabang yang lebih besar - melompat jika membawa bendera dan nol keduanya jelas.

Perhatikan bahwa dalam setiap kasus, modifikasi sangat sederhana , dan dapat diimplementasikan hanya dengan membuka atau mematikan sebagian kecil sirkuit, atau dengan menambahkan register bendera baru daripada yang dapat dikontrol oleh nilai yang perlu dihitung sebagai bagian dari implementasi instruksi tetap.

Oleh karena itu, biaya penambahan instruksi yang tidak ditandatangani sangat kecil . Mengenai mengapa hal itu harus dilakukan , perhatikan bahwa alamat memori (dan offset dalam array) secara inheren merupakan nilai yang tidak ditandatangani. Karena program menghabiskan banyak waktu memanipulasi alamat memori, memiliki tipe yang menanganinya dengan benar membuat program lebih mudah untuk ditulis.

Angka yang tidak ditandai ada sebagian besar untuk menangani situasi di mana seseorang membutuhkan cincin aljabar pembungkus (untuk tipe unsigned 16-bit, itu akan menjadi cincin integer congruent mod 65536). Ambil nilai, tambahkan jumlah yang kurang dari modulus, dan perbedaan antara dua nilai akan menjadi jumlah yang ditambahkan. Sebagai contoh dunia nyata, jika meter utilitas membaca 9995 pada awal bulan dan satu menggunakan 23 unit, meter tersebut akan membaca 0018 pada akhir bulan. Saat menggunakan tipe cincin aljabar, tidak perlu melakukan sesuatu yang khusus untuk mengatasi luapan. Mengurangi 9995 dari 0018 akan menghasilkan 0023, tepatnya jumlah unit yang digunakan.

Pada PDP-11, mesin yang menerapkan C pertama kali, tidak ada tipe integer yang tidak ditandatangani tetapi tipe yang ditandatangani dapat digunakan untuk aritmatika modular yang membungkus antara 32767 dan -32768 daripada antara 65535 dan 0. Instruksi integer pada beberapa lainnya platform tidak membungkus hal-hal dengan bersih, namun; Alih-alih mengharuskan implementasi harus meniru bilangan bulat pelengkap dua yang digunakan dalam PDP-11, bahasa itu malah menambahkan tipe yang tidak ditandatangani yang sebagian besar harus berperilaku sebagai cincin aljabar, dan memungkinkan tipe bilangan bulat yang ditandatangani berperilaku dengan cara lain jika meluap.

Pada hari-hari awal C, ada banyak jumlah yang bisa melebihi 32767 (INT_MAX umum) tetapi tidak 65535 (UINT_MAX umum). Dengan demikian menjadi umum untuk menggunakan tipe yang tidak ditandatangani untuk menampung jumlah seperti itu (misalnya size_t). Sayangnya, tidak ada dalam bahasa untuk membedakan antara jenis yang harus berperilaku seperti angka dengan sedikit rentang positif, dibandingkan jenis yang harus berperilaku seperti cincin aljabar. Alih-alih, bahasa membuat tipe lebih kecil dari angka "int" berperilaku seperti angka sedangkan tipe ukuran penuh berperilaku seperti cincin aljabar. Akibatnya, fungsi panggilan seperti:

uint32_t mul(uint16_t a, uint16_t b) { return a*b; }

dengan (65535, 65535) akan memiliki satu perilaku yang didefinisikan pada sistem di mana int16 bit (yaitu return 1), perilaku yang berbeda di mana int33 bit atau lebih besar (return 0xFFFE0001), dan Perilaku Tidak Terdefinisi pada sistem di mana "int" berada di mana saja di antara [perhatikan bahwa gcc biasanya akan menghasilkan hasil yang benar secara aritmatik dengan hasil antara INT_MAX + 1u dan UINT_MAX, tetapi terkadang akan menghasilkan kode untuk fungsi di atas yang gagal dengan nilai-nilai seperti itu!]. Tidak terlalu membantu.

Namun, kurangnya jenis yang berperilaku secara konsisten seperti angka atau secara konsisten seperti cincin aljabar tidak mengubah fakta bahwa jenis cincin aljabar hampir tidak bisa diabaikan untuk beberapa jenis pemrograman.