~ x + ~ y == ~ (x + y) selalu salah?

153

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 -5000dan 5000tetapi 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?

Steve
sumber
6
Apakah Anda ingin bukti atau sesuatu?
Alvin Wong
26
Ketahuilah bahwa dalam kasus integer overflow yang ditandatangani, ini adalah perilaku yang secara teknis tidak terdefinisi. Jadi dimungkinkan untuk kembali truebahkan jika mereka tidak pernah dapat mengasumsikan komplemen dua ketat.
Mysticial
1
@AlvinWong ya penjelasannya akan menyenangkan
Steve
1
@Steve: Anda dapat menunjukkan bahwa Anda telah mencoba semua tersangka biasa (-1, 0, 1, 2, dan seterusnya) di semua kombinasi, serta upaya Anda untuk "menyelesaikan" masalah untuk ukuran kata yang kecil ( tiga bit? empat bit?). Itu pasti akan membantu meyakinkan kita bahwa kita tidak hanya membantu seseorang mendapatkan sesuatu yang tidak mereka usahakan untuk diri mereka sendiri terlebih dahulu. :)
sarnold
4
@AlexLockwood Ketika saya pertama kali memposting pertanyaan, saya menganggap menandai pertanyaan sebagai "pekerjaan rumah" meminta orang untuk memberikan petunjuk untuk membantu saya memecahkan masalah (seperti yang dijelaskan oleh tag yang menyatakan "pekerjaan rumah") dan tidak hanya memberikan jawaban. Itu sebabnya saya langsung mengajukan pertanyaan masalah :)
Steve

Jawaban:

237

Asumsikan demi kontradiksi bahwa ada beberapa xdan beberapa y(mod 2 n ) sedemikian rupa

~(x+y) == ~x + ~y

Dengan komplemen dua *, kita tahu itu,

      -x == ~x + 1
<==>  -1 == ~x + x

Memperhatikan hasil ini, kami memiliki,

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

Karena itu, kontradiksi. Karena itu, ~(x+y) != ~x + ~yuntuk semua xdan y(mod 2 n ).


* Sangat menarik untuk dicatat bahwa pada mesin dengan aritmatika komplemen seseorang, kesetaraan sebenarnya berlaku untuk semua xdan y. Ini karena di bawah komplemen seseorang ~x = -x,. Jadi ~x + ~y == -x + -y == -(x+y) == ~(x+y),.

Alex Lockwood
sumber
47
Tentu saja, C tidak memerlukan perilaku ini; karena tidak memerlukan representasi komplemen dua.
Billy ONeal
12
Btw, kesetaraan itu berlaku untuk pelengkap seseorang. Operasi NOT tidak benar-benar didefinisikan untuk angka secara umum, jadi pencampuran TIDAK dengan hasil tambahan dalam perilaku yang berbeda tergantung pada representasi nomor.
nhahtdh
9
Orang bisa saja menyatakan kembali masalah menjadi untuk bilangan bulat unsigned dan kemudian dua komplemen tidak ikut bermain sama sekali.
R .. GitHub BERHENTI MEMBANTU ICE
5
Lebih sederhana lagi, IMHO:, ~x == -(x+1)jadi ~(x+y) == ~x + ~ytersirat -(x+y+1) == -(x+1) + -(y+1)menyiratkan-1 == -2
BlueRaja - Danny Pflughoeft
7
@ Billyilly, jangan khawatir, saya hanya bercanda dan saya menghargai Anda menyebutkannya :). Saya akan membelikan Anda minuman pada hari saya menemukan mesin yang melakukan aritmatika komplemen seseorang ... bagaimana itu terdengar? haha
Alex Lockwood
113

Dua komplemen

Pada sebagian besar komputer, jika xbilangan bulat, maka -xdinyatakan sebagai ~x + 1. Setara ~x == -(x + 1),. Membuat subtitusi ini dalam persamaan Anda memberi:

  • ~ x + ~ y == ~ (x + y)
  • - (x + 1) + - (y + 1) = - ((x + y) + 1)
  • -x - y - 2 = -x - y - 1
  • -2 = -1

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 , -xhanya direpresentasikan sebagai ~x. Nol adalah kasus khusus, memiliki representasi all-0's ( +0) dan all-1's ( -0), tetapi IIRC, C membutuhkan +0 == -0bahkan jika mereka memiliki pola bit yang berbeda, jadi ini seharusnya tidak menjadi masalah. Cukup gantikan ~dengan -.

  • ~ x + ~ y == ~ (x + y)
  • -x + (-y) = - (x + y)

yang berlaku untuk semua xdan y.

dan04
sumber
13
Memberi +1 untuk jawaban yang benar-benar mempertimbangkan pelengkap keduanya dan pelengkap seseorang atas dasar yang sama.
CVn
13
@ dan04 +0 == -0,. Akhirnya sesuatu yang masuk akal di C. :)
Alex Lockwood
32

Pertimbangkan hanya bit paling kanan dari keduanya xdan y(IE. Jika x == 13yang ada 1101di basis 2, kita hanya akan melihat bit terakhir, a 1) Lalu ada empat kemungkinan kasus:

x = 0, y = 0:

LHS: ~ 0 + ~ 0 => 1 + 1 => 10
RHS: ~ (0 + 0) => ~ 0 => 1

x = 0, y = 1:

LHS: ~ 0 + ~ 1 => 1 + 0 => 1
RHS: ~ (0 + 1) => ~ 1 => 0

x = 1, y = 0:

Saya akan menyerahkan ini kepada Anda karena ini adalah pekerjaan rumah (petunjuk: ini sama dengan yang sebelumnya dengan x dan y bertukar).

x = 1, y = 1:

Saya akan menyerahkan yang ini juga untuk Anda.

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.

Paul
sumber
27

Jika jumlah bit adalah n

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

Sekarang,

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

Karenanya, mereka akan selalu tidak setara, dengan selisih 1.

Karthik Kumar Viswanathan
sumber
4
@nhahtdh dan bagaimana Anda mendefinisikan ~operasi pada angka lebar tidak tetap?
hamstergene
1
Saya memberikan jawaban ini dengan jumlah bit ini sehingga mudah untuk dikorelasikan dengan apa yang diajarkan di kelas. Perhatikan bahwa ~ x sangat tergantung pada jumlah bit, n, yang digunakan untuk mewakili angka. Jadi masuk akal untuk tetap pada satu, ketika mencoba memverifikasi ini secara eksperimental.
Karthik Kumar Viswanathan
1
@hamstergene: Saya tahu bahwa jumlah bit sudah diperbaiki, tetapi poin saya adalah tidak harus sebesar itu (8, 16, dll.).
nhahtdh
1
Itu adalah nilai-nilai yang mudah untuk menulis sebuah program untuk memverifikasi jawabannya. Ia bekerja untuk setiap n, selama ~ x dan ~ y ditulis untuk mencocokkan yang diberikan.
Karthik Kumar Viswanathan
1
@hamstergene: Saya tidak punya masalah dengan buktinya, hanya saja angka-angka memberikan implikasi palsu bahwa itu hanya bekerja untuk kasus-kasus itu.
nhahtdh
27

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.

pengguna541686
sumber
2
Hanya pada mesin pelengkap dua. (Standar C tidak mengharuskan itu)
Billy ONeal
12
@Illy: Itu seperti mengatakan "hanya untuk orang-orang bersenjata dua".
dan04
2
@ dan04: Tidak. Saya ingin mengatakan bahwa semua tanda tangan yang ditandatangani dan representasi pelengkapnya telah hilang dari dunia. Tapi saya akan salah mengatakan itu. Standar C tidak memungkinkan Anda untuk membuat asumsi itu; oleh karena itu saya akan mengatakan kode yang membuat asumsi itu adalah kode yang buruk sebagian besar waktu. (Terutama ketika biasanya ada cara-cara yang lebih baik untuk mengacaukan angka-angka yang telah ditandatangani daripada sedikit memutar-mutar; dan terutama ketika angka-angka yang tidak ditandatangani mungkin merupakan pilihan yang lebih baik sebagian besar waktu itu)
Billy ONeal
10

Dalam komplemen satu dan dua (dan bahkan di 42), ini dapat dibuktikan:

~x + ~y == ~(x + a) + ~(y - a)

Sekarang biarkan a = ydan kita punya:

~x + ~y == ~(x + y) + ~(y - y)

atau:

~x + ~y == ~(x + y) + ~0

Karena itu dalam komplemen dua itu ~0 = -1, proposisi itu salah.

Dalam pelengkap seseorang itu ~0 = 0, proposisi itu benar.

ypercubeᵀᴹ
sumber
7

Menurut buku karya Dennis Ritchie, C tidak mengimplementasikan komplemen dua secara default. Karena itu, pertanyaan Anda mungkin tidak selalu benar.

pengguna1457474
sumber
5

Membiarkan MAX_INTint diwakili oleh 011111...111(karena betapapun banyaknya bit). Maka Anda tahu itu, ~x + x = MAX_INTdan ~y + y = MAX_INTkarena itu Anda akan tahu pasti bahwa perbedaan antara ~x + ~ydan ~(x + y)adalah 1.

Adrian Monk
sumber
5

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!

pengguna1422551
sumber
3

Tentu saja, C tidak memerlukan perilaku ini karena tidak memerlukan representasi komplemen dua. Misalnya, ~x = (2^n - 1) - x& ~y = (2^n - 1) - yakan mendapatkan hasil ini.

pengguna1472392
sumber
0

Ah, matematika diskrit mendasar!

Lihat Hukum De Morgan

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

Sangat penting untuk bukti Boolean!

David Kaczynski
sumber
Jelas salah. Dalam C + adalah tambahan, * perkalian dan bukan boolean atau atau dan.
nalply
Terima kasih telah menunjukkan operator yang salah, secara langsung. Sekarang telah diperbarui dengan operator yang benar, meskipun Anda benar karena tidak berlaku untuk pertanyaan awal.
David Kaczynski
1
Nah, jika benar adalah satu dan salah adalah nol, maka + dan * berperilaku persis seperti atau dan dan, apalagi komplemen dua berperilaku seperti tidak, maka hukum tetap berlaku.
a1an
Terima kasih telah menunjukkannya, aan. Saya mencoba memikirkan bagaimana Hukum De Morgan masih bisa diterapkan pada pertanyaan awal, tetapi sudah beberapa tahun sejak saya mempelajari baik pemrograman C atau Matematika Diskrit.
David Kaczynski