Apakah kode ini selalu bernilai false? Kedua variabel adalah int yang ditandatangani dua komplemen.
~x + ~y == ~(x + y)
Saya merasa harus ada beberapa nomor yang memenuhi persyaratan. Saya mencoba menguji angka antara -5000
dan 5000
tetapi tidak pernah mencapai kesetaraan. Apakah ada cara untuk membuat persamaan untuk menemukan solusi untuk kondisi tersebut?
Apakah bertukar satu dengan yang lain menyebabkan bug yang berbahaya dalam program saya?
true
bahkan jika mereka tidak pernah dapat mengasumsikan komplemen dua ketat.Jawaban:
Asumsikan demi kontradiksi bahwa ada beberapa
x
dan beberapay
(mod 2 n ) sedemikian rupaDengan komplemen dua *, kita tahu itu,
Memperhatikan hasil ini, kami memiliki,
Karena itu, kontradiksi. Karena itu,
~(x+y) != ~x + ~y
untuk semuax
dany
(mod 2 n ).* Sangat menarik untuk dicatat bahwa pada mesin dengan aritmatika komplemen seseorang, kesetaraan sebenarnya berlaku untuk semua
x
dany
. Ini karena di bawah komplemen seseorang~x = -x
,. Jadi~x + ~y == -x + -y == -(x+y) == ~(x+y)
,.sumber
~x == -(x+1)
jadi~(x+y) == ~x + ~y
tersirat-(x+y+1) == -(x+1) + -(y+1)
menyiratkan-1 == -2
Dua komplemen
Pada sebagian besar komputer, jika
x
bilangan bulat, maka-x
dinyatakan sebagai~x + 1
. Setara~x == -(x + 1)
,. Membuat subtitusi ini dalam persamaan Anda memberi:yang merupakan kontradiksi, jadi
~x + ~y == ~(x + y)
selalu salah .Yang mengatakan, para pedant akan menunjukkan bahwa C tidak memerlukan pelengkap dua, jadi kita juga harus mempertimbangkan ...
Komplemen seseorang
Dalam pelengkap seseorang ,
-x
hanya direpresentasikan sebagai~x
. Nol adalah kasus khusus, memiliki representasi all-0's (+0
) dan all-1's (-0
), tetapi IIRC, C membutuhkan+0 == -0
bahkan jika mereka memiliki pola bit yang berbeda, jadi ini seharusnya tidak menjadi masalah. Cukup gantikan~
dengan-
.yang berlaku untuk semua
x
dany
.sumber
+0 == -0
,. Akhirnya sesuatu yang masuk akal di C. :)Pertimbangkan hanya bit paling kanan dari keduanya
x
dany
(IE. Jikax == 13
yang ada1101
di basis 2, kita hanya akan melihat bit terakhir, a1
) Lalu ada empat kemungkinan kasus:x = 0, y = 0:
x = 0, y = 1:
x = 1, y = 0:
x = 1, y = 1:
Anda dapat menunjukkan bahwa bit paling kanan akan selalu berbeda di Sisi Kiri dan Sisi Kanan dari persamaan yang diberikan input apa pun, jadi Anda telah membuktikan bahwa kedua belah pihak tidak sama, karena mereka memiliki setidaknya satu bit yang dibalik dari satu orang ke orang lainnya.
sumber
Jika jumlah bit adalah n
Sekarang,
Karenanya, mereka akan selalu tidak setara, dengan selisih 1.
sumber
~
operasi pada angka lebar tidak tetap?Petunjuk:
x + ~x = -1
(mod 2 n )Dengan asumsi tujuan dari pertanyaan ini adalah menguji matematika Anda (daripada keterampilan membaca-C-spesifikasi Anda), ini akan membuat Anda mendapatkan jawabannya.
sumber
Dalam komplemen satu dan dua (dan bahkan di 42), ini dapat dibuktikan:
Sekarang biarkan
a = y
dan kita punya:atau:
Karena itu dalam komplemen dua itu
~0 = -1
, proposisi itu salah.Dalam pelengkap seseorang itu
~0 = 0
, proposisi itu benar.sumber
Menurut buku karya Dennis Ritchie, C tidak mengimplementasikan komplemen dua secara default. Karena itu, pertanyaan Anda mungkin tidak selalu benar.
sumber
Membiarkan
MAX_INT
int diwakili oleh011111...111
(karena betapapun banyaknya bit). Maka Anda tahu itu,~x + x = MAX_INT
dan~y + y = MAX_INT
karena itu Anda akan tahu pasti bahwa perbedaan antara~x + ~y
dan~(x + y)
adalah1
.sumber
C tidak mensyaratkan bahwa komplemen dua menjadi apa yang diterapkan. Namun, untuk integer unsigned, logika yang serupa diterapkan. Perbedaan akan selalu menjadi 1 di bawah logika ini!
sumber
Tentu saja, C tidak memerlukan perilaku ini karena tidak memerlukan representasi komplemen dua. Misalnya,
~x = (2^n - 1) - x
&~y = (2^n - 1) - y
akan mendapatkan hasil ini.sumber
Ah, matematika diskrit mendasar!
Lihat Hukum De Morgan
Sangat penting untuk bukti Boolean!
sumber