Pemeran unsigned-to-signed yang efisien menghindari perilaku yang ditentukan oleh implementasi

Saya ingin mendefinisikan fungsi yang mengambil unsigned intargumen sebagai dan mengembalikan intmodulo UINT_MAX + 1 yang kongruen ke argumen.

Upaya pertama mungkin terlihat seperti ini:

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

Tapi seperti yang diketahui pengacara bahasa, casting dari unsigned ke signed untuk nilai yang lebih besar dari INT_MAX adalah definisi implementasi.

Saya ingin menerapkan ini sedemikian rupa sehingga (a) hanya bergantung pada perilaku yang diamanatkan oleh spesifikasi; dan (b) mengkompilasi menjadi no-op pada mesin modern manapun dan mengoptimalkan compiler.

Adapun mesin aneh ... Jika tidak ada modulo kongruen int ditandatangani UINT_MAX + 1 ke int unsigned, katakanlah saya ingin melempar pengecualian. Jika ada lebih dari satu (saya tidak yakin ini mungkin), katakanlah saya ingin yang terbesar.

Oke, upaya kedua:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

Saya tidak terlalu peduli dengan efisiensi ketika saya tidak menggunakan sistem pelengkap dua, karena menurut pendapat saya yang sederhana itu tidak mungkin. Dan jika kode saya menjadi hambatan pada sistem magnitudo tanda yang ada di mana-mana pada tahun 2050, saya yakin seseorang dapat mengetahuinya dan mengoptimalkannya saat itu.

Sekarang, upaya kedua ini hampir mendekati apa yang saya inginkan. Meskipun transmisi ke intditentukan oleh implementasi untuk beberapa masukan, transmisi kembali ke unsigneddijamin oleh standar untuk mempertahankan nilai modulo UINT_MAX + 1. Jadi kondisional memeriksa dengan tepat apa yang saya inginkan, dan tidak akan terkompilasi menjadi apa pun di sistem apa pun yang mungkin saya temui.

Namun ... Saya masih mentransmisikan ke inttanpa terlebih dahulu memeriksa apakah itu akan memanggil perilaku yang ditentukan implementasi. Pada beberapa sistem hipotetis di tahun 2050, ia dapat melakukan entah apa. Jadi katakanlah saya ingin menghindari itu.

Pertanyaan: Seperti apa tampilan "percobaan ketiga" saya?

Sebagai ringkasan, saya ingin:

• Transmisikan dari unsigned int ke signed int
• Pertahankan nilai mod UINT_MAX + 1
• Gunakan hanya perilaku yang diamanatkan standar
• Kompilasi menjadi no-op pada mesin pelengkap dua tipikal dengan pengoptimal kompiler

[Memperbarui]

Izinkan saya memberi contoh untuk menunjukkan mengapa ini bukan pertanyaan yang sepele.

Pertimbangkan implementasi hipotetis C ++ dengan properti berikut:

• sizeof(int) sama dengan 4
• sizeof(unsigned) sama dengan 4
• INT_MAX sama dengan 32767
• INT_MINsama dengan -2 ³² + 32768
• UINT_MAXsama dengan 2 ³² - 1
• Aritmatika aktif intadalah modulo 2 ³² (ke dalam kisaran INT_MINmelalui INT_MAX)
• std::numeric_limits<int>::is_modulo adalah benar
• Casting unsigned nto int mempertahankan nilai untuk 0 <= n <= 32767 dan sebaliknya menghasilkan nol

Pada implementasi hipotetis ini, terdapat tepat satu intnilai kongruen (mod UINT_MAX + 1) untuk setiap unsignednilai. Jadi pertanyaan saya akan terdefinisi dengan baik.

Saya mengklaim bahwa implementasi C ++ hipotetis ini sepenuhnya sesuai dengan spesifikasi C ++ 98, C ++ 03, dan C ++ 11. Saya akui saya belum menghafal setiap kata dari semuanya ... Tapi saya yakin saya telah membaca bagian yang relevan dengan cermat. Jadi jika Anda ingin saya menerima jawaban Anda, Anda harus (a) mengutip spesifikasi yang mengesampingkan implementasi hipotetis ini atau (b) menanganinya dengan benar.

Memang, jawaban yang benar harus menangani setiap implementasi hipotetis yang diizinkan oleh standar. Itulah yang dimaksud dengan "hanya menjalankan perilaku yang diamanatkan standar", menurut definisi.

Secara kebetulan, catatan yang std::numeric_limits<int>::is_modulosama sekali tidak berguna di sini karena berbagai alasan. Untuk satu hal, bisa jadi truebahkan jika cast unsigned-to-signed tidak berfungsi untuk nilai unsigned yang besar. Untuk yang lain, itu bisa truebahkan pada sistem-komplemen atau besaran-tanda, jika aritmatika hanyalah modulo seluruh rentang bilangan bulat. Dan seterusnya. Jika jawaban Anda bergantung pada is_modulo, itu salah.

[Perbarui 2]

Jawaban hvd mengajari saya sesuatu: Implementasi hipotetis C ++ saya untuk bilangan bulat tidak diizinkan oleh C modern. Standar C99 dan C11 sangat spesifik tentang representasi bilangan bulat yang ditandatangani; memang, mereka hanya mengizinkan dua-pelengkap, pelengkap satu, dan besaran tanda (bagian 6.2.6.2 ayat (2);).

Tapi C ++ bukanlah C. Ternyata, fakta ini menjadi inti dari pertanyaan saya.

Standar C ++ 98 asli didasarkan pada C89 yang jauh lebih tua, yang mengatakan (bagian 3.1.2.5):

Untuk setiap jenis bilangan bulat bertanda, ada jenis bilangan bulat unsigned yang sesuai (tetapi berbeda) (ditetapkan dengan kata kunci unsigned) yang menggunakan jumlah penyimpanan yang sama (termasuk informasi tanda) dan memiliki persyaratan penyelarasan yang sama. Rentang nilai nonnegatif dari tipe integer bertanda adalah subrange dari tipe integer unsigned yang sesuai, dan representasi nilai yang sama di setiap tipe adalah sama.

C89 tidak mengatakan apa-apa tentang hanya memiliki satu tanda bit atau hanya mengizinkan dua-pelengkap / satu-pelengkap / besaran-tanda.

Standar C ++ 98 mengadopsi bahasa ini hampir kata demi kata (bagian 3.9.1 paragraf (3)):

Untuk setiap jenis bilangan bulat bertanda, terdapat jenis bilangan bulat unsigned yang sesuai (tetapi berbeda) : " unsigned char", " unsigned short int", " unsigned int", dan " unsigned long int", yang masing-masing menempati jumlah penyimpanan yang sama dan memiliki persyaratan penyelarasan yang sama (3.9 ) sebagai jenis bilangan bulat bertanda tangan yang sesuai; artinya, setiap tipe integer bertanda memiliki representasi objek yang sama dengan tipe integer unsigned yang sesuai . Rentang nilai nonnegatif dari tipe bilangan bulat bertanda adalah subrentang dari jenis bilangan bulat tak bertanda yang sesuai, dan representasi nilai dari setiap jenis bertanda tangan / tak bertanda tangan harus sama.

Standar C ++ 03 menggunakan bahasa yang pada dasarnya identik, seperti halnya C ++ 11.

Tidak ada spesifikasi C ++ standar yang membatasi representasi integer yang ditandatangani ke spesifikasi C apa pun, sejauh yang saya tahu. Dan tidak ada yang mengamanatkan sedikit pun tanda atau semacamnya. Semua yang dikatakan adalah bahwa bilangan bulat bertanda non-negatif harus menjadi subrentang dari unsigned yang sesuai.

Jadi, sekali lagi saya mengklaim bahwa INT_MAX = 32767 dengan INT_MIN = -2 ³² +32768 diizinkan. Jika jawaban Anda mengasumsikan sebaliknya, itu tidak benar kecuali Anda mengutip standar C ++ yang membuktikan bahwa saya salah.

Memperluas jawaban pengguna71404:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

Jika x >= INT_MIN(perhatikan aturan promosi, INT_MINakan diubah menjadi unsigned), makax - INT_MIN <= INT_MAX , ini tidak akan melimpah.

Jika tidak jelas, lihat klaim "Jika x >= -4u, maka x + 4 <= 3", dan perlu diingat bahwa INT_MAXitu setidaknya akan sama dengan nilai matematika -INT_MIN - 1.

Pada sistem yang paling umum, di mana !(x <= INT_MAX)tersirat x >= INT_MIN, pengoptimal harus dapat (dan pada sistem saya, mampu) untuk menghapus pemeriksaan kedua, menentukan bahwa dua returnpernyataan dapat dikompilasi ke kode yang sama, dan menghapus pemeriksaan pertama juga. Daftar perakitan yang dihasilkan:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

Implementasi hipotetis dalam pertanyaan Anda:

• INT_MAX sama dengan 32767
• INT_MIN sama dengan -2 ³² + 32768

tidak memungkinkan, sehingga tidak perlu pertimbangan khusus. INT_MINakan sama dengan salah satu -INT_MAX, atau dengan -INT_MAX - 1. Ini mengikuti representasi C dari tipe integer (6.2.6.2), yang membutuhkan nbit menjadi bit nilai, satu bit menjadi bit tanda, dan hanya mengizinkan satu representasi jebakan tunggal (tidak termasuk representasi yang tidak valid karena bit padding), yaitu salah satu yang sebaliknya akan mewakili nol negatif / -INT_MAX - 1. C ++ tidak mengizinkan representasi integer apa pun di luar yang diizinkan C.

Pembaruan : Kompiler Microsoft tampaknya tidak memperhatikan itux > 10danx >= 11menguji hal yang sama. Ini hanya menghasilkan kode yang diinginkan jikax >= INT_MINdiganti denganx > INT_MIN - 1u, yang dapat dideteksi sebagai negasix <= INT_MAX (pada platform ini).

[Update dari penanya (Nemo), menguraikan diskusi kita di bawah]

Sekarang saya percaya jawaban ini berfungsi di semua kasus, tetapi untuk alasan yang rumit. Saya kemungkinan akan memberikan hadiah untuk solusi ini, tetapi saya ingin menangkap semua detail berdarah jika ada yang peduli.

Mari kita mulai dengan C ++ 11, bagian 18.3.3:

Tabel 31 menjelaskan header <climits> .

...

Isinya sama dengan header pustaka C Standar <limits.h>.

Di sini, "Standar C" berarti C99, yang spesifikasinya sangat membatasi representasi bilangan bulat bertanda. Mereka seperti integer unsigned, tetapi dengan satu bit didedikasikan untuk "sign" dan nol atau lebih bit yang didedikasikan untuk "padding". Bit padding tidak berkontribusi pada nilai integer, dan bit tanda hanya berkontribusi sebagai pelengkap dua, pelengkap satu, atau besaran tanda.

Karena C ++ 11 mewarisi <climits> makro dari C99, INT_MIN adalah -INT_MAX atau -INT_MAX-1, dan kode hvd dijamin berfungsi. (Perhatikan bahwa, karena padding, INT_MAX bisa jauh lebih kecil dari UINT_MAX / 2 ... Tapi berkat cara kerja cast yang ditandatangani-> unsigned, jawaban ini menangani hal itu dengan baik.)

C ++ 03 / C ++ 98 lebih rumit. Ini menggunakan kata-kata yang sama untuk mewarisi <climits>dari "Standar C", tapi sekarang "Standar C" berarti C89 / C90.

Semua ini - C ++ 98, C ++ 03, C89 / C90 - memiliki kata-kata yang saya berikan dalam pertanyaan saya, tetapi juga menyertakan ini (C ++ 03 bagian 3.9.1 paragraf 7):

Representasi tipe integral harus mendefinisikan nilai dengan menggunakan sistem penomoran biner murni. [44) [ Contoh : Standar Internasional ini mengizinkan komplemen 2, komplemen 1, dan representasi besaran bertanda tangan untuk tipe integral.]

Catatan kaki (44) mendefinisikan "sistem penomoran biner murni":

Representasi posisi untuk bilangan bulat yang menggunakan digit biner 0 dan 1, di mana nilai yang diwakili oleh bit yang berurutan adalah aditif, dimulai dengan 1, dan dikalikan dengan pangkat integral berurutan dari 2, kecuali mungkin untuk bit dengan posisi tertinggi.

Yang menarik dari kata-kata ini adalah bahwa ia bertentangan dengan dirinya sendiri, karena definisi "sistem penomoran biner murni" tidak mengizinkan representasi tanda / besaran! Itu memungkinkan bit tinggi memiliki, katakanlah, nilai -2 ^n-1 (pelengkap dua) atau - (2 ^n-1 -1) (pelengkap satu). Tetapi tidak ada nilai untuk bit tinggi yang menghasilkan tanda / magnitudo.

Bagaimanapun, "implementasi hipotetis" saya tidak memenuhi syarat sebagai "biner murni" di bawah definisi ini, jadi itu dikesampingkan.

Namun, fakta bahwa bit tinggi adalah spesial berarti kita dapat membayangkannya memberikan kontribusi nilai apa pun: Nilai positif kecil, nilai positif besar, nilai negatif kecil, atau nilai negatif besar. (Jika bit tanda dapat berkontribusi - (2 ^n-1 -1), mengapa tidak - (2 ^n-1 -2)? Dll.)

Jadi, mari kita bayangkan representasi integer bertanda yang memberikan nilai aneh ke bit "tanda".

Nilai positif kecil untuk bit tanda akan menghasilkan kisaran positif untuk int(mungkin sebesar unsigned), dan kode hvd menangani itu dengan baik.

Nilai positif yang sangat besar untuk bit tanda akan menghasilkan intnilai maksimum yang lebih besar dari unsigned, yang dilarang.

Nilai negatif yang sangat besar untuk bit tanda akan menghasilkan intrepresentasi rentang nilai yang tidak bersebelahan, dan kata-kata lain dalam spesifikasi mengesampingkan.

Akhirnya, bagaimana dengan bit tanda yang menyumbang sejumlah kecil negatif? Bisakah kita memiliki 1 di "bit tanda" yang berkontribusi, katakanlah, -37 ke nilai int? Jadi INT_MAX akan menjadi (katakanlah) 2 ³¹ -1 dan INT_MIN akan menjadi -37?

Ini akan menghasilkan beberapa bilangan yang memiliki dua representasi ... Tapi komplemen satu memberikan dua representasi menjadi nol, dan itu diperbolehkan menurut "Contoh". Tidak ada spesifikasi yang mengatakan bahwa nol adalah satu - satunya bilangan bulat yang mungkin memiliki dua representasi. Jadi saya pikir hipotesis baru ini diizinkan oleh spesifikasi.

Memang, nilai negatif apa pun dari -1 ke bawah hingga -INT_MAX-1tampaknya diizinkan sebagai nilai untuk "bit tanda", tetapi tidak ada yang lebih kecil (jangan sampai rentangnya tidak bersebelahan). Dengan kata lain, INT_MINmungkin apa saja mulai dari -INT_MAX-1-1.

Sekarang coba tebak? Untuk cast kedua dalam kode hvd untuk menghindari perilaku yang ditentukan implementasi, kita hanya perlu x - (unsigned)INT_MINkurang dari atau sama dengan INT_MAX. Kami baru saja menunjukkan INT_MINsetidaknya -INT_MAX-1. Jelas, xpaling banyak UINT_MAX. Mentransmisikan angka negatif ke unsigned sama dengan menambahkan UINT_MAX+1. Gabungkan semuanya:

x - (unsigned)INT_MIN <= INT_MAX

jika dan hanya jika

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

Yang terakhir adalah apa yang baru saja kami tunjukkan, jadi bahkan dalam kasus yang menyimpang ini, kode itu benar-benar berfungsi.

Itu menghabiskan semua kemungkinan, sehingga mengakhiri latihan yang sangat akademis ini.

Intinya: Ada beberapa perilaku serius yang kurang ditentukan untuk integer yang ditandatangani di C89 / C90 yang diwarisi oleh C ++ 98 / C ++ 03. Itu diperbaiki di C99, dan C ++ 11 secara tidak langsung mewarisi perbaikan dengan memasukkan <limits.h>dari C99. Tetapi bahkan C ++ 11 mempertahankan kata-kata "representasi biner murni" yang kontradiktif ...

Kode ini hanya bergantung pada perilaku, yang diamanatkan oleh spesifikasi, sehingga persyaratan (a) mudah dipenuhi:

int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}

Tidak mudah dengan persyaratan (b). Ini dikompilasi menjadi no-op dengan gcc 4.6.3 (-Os, -O2, -O3) dan dengan clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 menolak untuk mengoptimalkan ini. Dan saya tidak punya info tentang Visual C.

Jawaban asli memecahkan masalah hanya untuk unsigned=>int . Bagaimana jika kita ingin menyelesaikan masalah umum dari "beberapa jenis yang tidak bertanda tangan" ke jenis bertanda yang sesuai? Selain itu, jawaban asli sangat bagus dalam mengutip bagian-bagian standar dan menganalisis beberapa kasus sudut, tetapi itu tidak benar-benar membantu saya memahami mengapa ini berhasil, jadi jawaban ini akan mencoba memberikan dasar konseptual yang kuat. Jawaban ini akan mencoba membantu menjelaskan "mengapa", dan menggunakan fitur C ++ modern untuk mencoba menyederhanakan kode.

Jawaban C ++ 20

Masalahnya telah disederhanakan secara dramatis dengan P0907: Integer yang Ditandatangani adalah Pelengkap Dua dan kata-kata terakhir P1236 yang dipilih ke dalam standar C ++ 20. Sekarang, jawabannya sesederhana mungkin:

template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
    return static_cast<std::make_signed_t<T>>(value);
}

Itu dia. SEBUAHstatic_cast (atau C-style cast) akhirnya dijamin melakukan hal yang Anda perlukan untuk pertanyaan ini, dan hal yang selalu dipikirkan oleh banyak programmer.

Jawaban C ++ 17

Di C ++ 17, semuanya jauh lebih rumit. Kita harus berurusan dengan tiga kemungkinan representasi bilangan bulat (komplemen dua, komplemen satu, dan besaran tanda). Bahkan dalam kasus di mana kita tahu itu harus menjadi pelengkap dua karena kita memeriksa kisaran nilai yang mungkin, konversi nilai di luar kisaran bilangan bulat bertanda ke bilangan bulat bertanda tersebut masih memberi kita hasil yang ditentukan implementasi. Kita harus menggunakan trik seperti yang kita lihat di jawaban lain.

Pertama, berikut adalah kode cara menyelesaikan masalah secara umum:

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using result = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<T>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<result>(value);
    } else {
        using promoted_unsigned = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
        using promoted_signed = std::make_signed_t<promoted_unsigned>;
        constexpr auto shift_by_window = [](auto x) {
            // static_cast to avoid conversion warning
            return x - static_cast<decltype(x)>(result_limits::max()) - 1;
        };
        return static_cast<result>(
            shift_by_window( // shift values from common range to negative range
                static_cast<promoted_signed>(
                    shift_by_window( // shift large values into common range
                        static_cast<promoted_unsigned>(value) // cast to avoid promotion to int
                    )
                )
            )
        );
    }
}

Ini memiliki lebih banyak pemeran daripada jawaban yang diterima, dan itu untuk memastikan tidak ada peringatan ketidakcocokan yang ditandatangani / tidak bertanda tangan dari compiler Anda dan untuk menangani aturan promosi bilangan bulat dengan benar.

Pertama-tama kita memiliki kasus khusus untuk sistem yang bukan merupakan komplemen dua (dan dengan demikian kita harus menangani nilai maksimum yang mungkin secara khusus karena tidak memiliki apa pun untuk dipetakan). Setelah itu, kita masuk ke algoritma sebenarnya.

Ketentuan tingkat atas kedua sangat mudah: kita tahu nilainya kurang dari atau sama dengan nilai maksimum, sehingga cocok dengan jenis hasil. Kondisi ketiga sedikit lebih rumit bahkan dengan komentar, jadi beberapa contoh mungkin akan membantu memahami mengapa setiap pernyataan diperlukan.

Dasar konseptual: garis bilangan

Pertama, windowkonsep apa ini ? Perhatikan garis bilangan berikut:

   |   signed   |
<.........................>
          |  unsigned  |

Ternyata untuk bilangan bulat komplemen dua, Anda dapat membagi himpunan bagian dari garis bilangan yang dapat dijangkau oleh salah satu jenis menjadi tiga kategori yang berukuran sama:

- => signed only
= => both
+ => unsigned only

<..-------=======+++++++..>

Ini dapat dengan mudah dibuktikan dengan mempertimbangkan representasi. Integer dimulai unsigned di 0dan penggunaan semua bit untuk meningkatkan nilai dalam kekuatan dari 2. integer ditandatangani adalah persis sama untuk semua bit kecuali bit tanda, yang bernilai -(2^position)bukan 2^position. Ini berarti bahwa untuk semua n - 1bit, mereka mewakili nilai yang sama. Kemudian, unsigned integer memiliki satu bit normal lagi, yang menggandakan jumlah total nilai (dengan kata lain, ada banyak nilai dengan bit yang disetel seperti jika tidak disetel). Logika yang sama berlaku untuk bilangan bulat bertanda, kecuali bahwa semua nilai dengan kumpulan bit itu negatif.

Dua representasi bilangan bulat hukum lainnya, komplemen dan besaran tanda satu, memiliki semua nilai yang sama dengan bilangan bulat pelengkap dua kecuali satu: nilai paling negatif. C ++ mendefinisikan segala sesuatu tentang tipe integer, kecuali reinterpret_cast(dan C ++ 20 std::bit_cast), dalam hal rentang nilai yang dapat direpresentasikan, bukan dalam hal representasi bit. Ini berarti bahwa analisis kita akan berlaku untuk masing-masing dari ketiga representasi ini selama kita tidak pernah mencoba membuat representasi jebakan. Nilai unsigned yang akan memetakan ke nilai yang hilang ini agak disayangkan: nilai yang berada tepat di tengah nilai unsigned. Untungnya, kondisi pertama kita memeriksa (pada waktu kompilasi) apakah representasi seperti itu ada, lalu menanganinya secara khusus dengan pemeriksaan waktu proses.

Kondisi pertama menangani kasus di mana kita berada di =bagian, yang berarti kita berada di wilayah yang tumpang tindih di mana nilai di satu dapat direpresentasikan di bagian lain tanpa perubahan. The wilayah) sehingga kita memiliki pemetaan yang unik lagi.shift_by_window fungsi dalam kode bergerak semua nilai turun dengan ukuran masing-masing segmen ini (kita harus mengurangi nilai max kemudian mengurangi 1 untuk menghindari masalah meluap aritmatika). Kalau kita berada di luar daerah itu (kita berada di+ wilayah tersebut), kita perlu melompat ke bawah dengan satu ukuran jendela. Ini menempatkan kami pada rentang yang tumpang tindih, yang berarti kami dapat dengan aman mengonversi dari unsigned menjadi signed karena tidak ada perubahan nilai. Namun, kami belum selesai karena kami telah memetakan dua nilai unsigned ke setiap nilai yang ditandatangani. Oleh karena itu, kita perlu menggeser ke bawah ke jendela berikutnya (-

Sekarang, apakah ini memberi kita hasil mod yang sesuai UINT_MAX + 1, seperti yang diminta dalam pertanyaan? UINT_MAX + 1setara dengan 2^n, di mana njumlah bit dalam representasi nilai. Nilai yang kita gunakan untuk ukuran jendela kita sama dengan 2^(n - 1)(indeks akhir dalam urutan nilai kurang dari ukuran). Kami mengurangi nilai itu dua kali, yang berarti kami mengurangi 2 * 2^(n - 1)yang sama dengan 2^n. Menambah dan mengurangi xadalah no-op dalam mod aritmatika x, jadi kami tidak mempengaruhi mod nilai asli 2^n.

Menangani promosi integer dengan benar

Karena ini adalah fungsi umum dan bukan hanya intdan unsigned, kita juga harus memperhatikan aturan promosi yang tidak terpisahkan. Ada dua kasus yang mungkin menarik: satu di mana shortlebih kecil dari intdan satu di mana shortukurannya sama dengan int.

Contoh: shortlebih kecil dariint

Jika shortlebih kecil dari int(umum pada platform modern) maka kita juga tahu bahwa unsigned shortdapat muat di int, yang berarti bahwa setiap operasi di atasnya akan benar-benar terjadi int, jadi kami secara eksplisit mentransmisikan ke jenis yang dipromosikan untuk menghindari hal ini. Pernyataan terakhir kita cukup abstrak dan menjadi lebih mudah dipahami jika kita menggantinya dengan nilai nyata. Untuk kasus pertama yang menarik, tanpa kehilangan keumuman, mari kita pertimbangkan 16-bit shortdan 17-bit int(yang masih diperbolehkan di bawah aturan baru, dan hanya akan berarti bahwa setidaknya satu dari dua tipe integer memiliki beberapa bit padding ):

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int17_t>(
            shift_by_window(
                static_cast<uint17_t>(value)
            )
        )
    )
);

Memecahkan kemungkinan nilai unsigned 16-bit terbesar

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return int16_t(
    shift_by_window(
        int17_t(
            shift_by_window(
                uint17_t(65535)
            )
        )
    )
);

Menyederhanakan menjadi

return int16_t(
    int17_t(
        uint17_t(65535) - uint17_t(32767) - 1
    ) -
    int17_t(32767) -
    1
);

Menyederhanakan menjadi

return int16_t(
    int17_t(uint17_t(32767)) -
    int17_t(32767) -
    1
);

Menyederhanakan menjadi

return int16_t(
    int17_t(32767) -
    int17_t(32767) -
    1
);

Menyederhanakan menjadi

return int16_t(-1);

Kami memasukkan sebanyak mungkin unsigned dan kembali -1, sukses!

Contoh: shortukuran yang sama sepertiint

Jika shortukurannya sama dengan int(tidak umum di platform modern), aturan promosi integral akan sedikit berbeda. Dalam hal ini, shortpromosikan ke intdan unsigned shortpromosikan ke unsigned. Untungnya, kami secara eksplisit mentransmisikan setiap hasil ke jenis yang ingin kami hitung, jadi kami tidak mendapatkan promosi yang bermasalah. Tanpa kehilangan keumuman, mari kita pertimbangkan 16-bit shortdan 16-bit int:

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int16_t>(
            shift_by_window(
                static_cast<uint16_t>(value)
            )
        )
    )
);

Memecahkan kemungkinan nilai unsigned 16-bit terbesar

auto x = int16_t(
    uint16_t(65535) - uint16_t(32767) - 1
);
return int16_t(
    x - int16_t(32767) - 1
);

Menyederhanakan menjadi

return int16_t(
    int16_t(32767) - int16_t(32767) - 1
);

Menyederhanakan menjadi

return int16_t(-1);

Kami memasukkan sebanyak mungkin unsigned dan kembali -1, sukses!

Bagaimana jika saya hanya peduli intdan unsigneddan tidak peduli dengan peringatan, seperti pertanyaan aslinya?

constexpr int cast_to_signed_integer(unsigned const value) {
    using result_limits = std::numeric_limits<int>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<unsigned>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<int>(value);
    } else {
        constexpr int window = result_limits::min();
        return static_cast<int>(value + window) + window;
    }
}

Lihat secara langsung

https://godbolt.org/z/74hY81

Di sini kita melihat bahwa clang, gcc, dan icc tidak menghasilkan kode untuk castdan cast_to_signed_integer_basicdi -O2dan -O3, dan MSVC tidak menghasilkan kode di /O2, jadi solusinya optimal.

Anda dapat secara eksplisit memberi tahu compiler apa yang ingin Anda lakukan:

int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}

Dikompilasi dengan gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) hingga

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Jika xmasukan kami ...

Jika x > INT_MAX, kita ingin mencari konstan ksehingga 0< x - k*INT_MAX< INT_MAX.

Ini mudah - unsigned int k = x / INT_MAX;. Kalau begitu, biarkanunsigned int x2 = x - k*INT_MAX;

Sekarang kami dapat melakukan cast x2dengan intaman. Membiarkanint x3 = static_cast<int>(x2);

Kami sekarang ingin mengurangi sesuatu seperti UINT_MAX - k * INT_MAX + 1dari x3, jika k > 0.

Sekarang, pada sistem pelengkap 2, selama x > INT_MAX, ini berhasil untuk:

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

Perhatikan bahwa UINT_MAX+1nol dalam jaminan C ++, konversi ke int adalah noop, dan kami mengurangik*INT_MAX lalu menambahkannya kembali pada "nilai yang sama". Jadi pengoptimal yang dapat diterima harus mampu menghapus semua kebodohan itu!

Itu menyisakan masalah x > INT_MAXatau tidak. Nah, kami membuat 2 cabang, satu dengan x > INT_MAX, dan satu tanpa. Yang tanpa melakukan cast strait, yang dioptimalkan oleh compiler ke noop. Yang dengan ... melakukan noop setelah pengoptimal selesai. Pengoptimal cerdas menyadari kedua cabang pada hal yang sama, dan menjatuhkan cabang.

Masalah: jika UINT_MAXrelatif sangat besar INT_MAX, hal di atas mungkin tidak berfungsi. Saya berasumsi bahwa k*INT_MAX <= UINT_MAX+1secara implisit.

Kami mungkin bisa menyerang ini dengan beberapa enum seperti:

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

yang berhasil ke 2 dan 1 pada sistem pelengkap 2 saya percaya (apakah kita dijamin untuk matematika itu berfungsi? Itu rumit ...), dan melakukan logika berdasarkan ini yang dengan mudah mengoptimalkannya pada sistem pelengkap non-2 ...

Ini juga membuka kasus pengecualian. Ini hanya mungkin jika UINT_MAX jauh lebih besar dari (INT_MIN-INT_MAX), jadi Anda dapat meletakkan kode pengecualian Anda di blok if yang menanyakan pertanyaan itu dengan tepat, dan itu tidak akan memperlambat Anda pada sistem tradisional.

Saya tidak begitu yakin bagaimana membangun konstanta waktu kompilasi untuk menangani hal itu dengan benar.

std::numeric_limits<int>::is_moduloadalah konstanta waktu kompilasi. sehingga Anda dapat menggunakannya untuk spesialisasi template. masalah terpecahkan, setidaknya jika kompiler bermain bersama dengan inlining.

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

Saya pikir tipe int setidaknya dua byte, jadi INT_MIN dan INT_MAX dapat berubah di platform yang berbeda.

Tipe dasar

≤climits≥ header

Uang saya menggunakan memcpy. Kompiler yang baik tahu cara mengoptimalkannya:

#include <stdio.h>
#include <memory.h>
#include <limits.h>

static inline int unsigned_to_signed(unsigned n)
{
    int result;
    memcpy( &result, &n, sizeof(result));
    return result;
}

int main(int argc, const char * argv[])
{
    unsigned int x = UINT_MAX - 1;
    int xx = unsigned_to_signed(x);
    return xx;
}

Bagi saya (Xcode 8.3.2, Apple LLVM 8.1, -O3), yang menghasilkan:

_main:                                  ## @main
Lfunc_begin0:
    .loc    1 21 0                  ## /Users/Someone/main.c:21:0
    .cfi_startproc
## BB#0:
    pushq    %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    ##DEBUG_VALUE: main:argc <- %EDI
    ##DEBUG_VALUE: main:argv <- %RSI
Ltmp3:
    ##DEBUG_VALUE: main:x <- 2147483646
    ##DEBUG_VALUE: main:xx <- 2147483646
    .loc    1 24 5 prologue_end     ## /Users/Someone/main.c:24:5
    movl    $-2, %eax
    popq    %rbp
    retq
Ltmp4:
Lfunc_end0:
    .cfi_endproc