Re: [問題] 為什麼互為2的補數的兩個數字，必定是相

看板C_and_CPP (C/C++)作者a58524andy (就先這樣吧)時間2年前 (2021/05/12 07:14)推噓1(2推 1噓 6→)

留言9則, 8人參與討論串2/2 (看更多)

※ 引述《lueichun (= =)》之銘言： : : 如題，為什麼互為2的補數的兩個數字，彼此一定是相反數呢？ : : 例如0101=5 那麼1011就=-5 : : 01111111=127 那麼10000001就=-127 : : 請問為什麼會這樣呢？ : : -- : ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.167.40.196 (臺灣) : ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1620734284.A.680.html : : 推 ucrxzero: 定義 05/11 21:01 我的理解上這其實是個有些有趣的問題而不只是定義上怎麼做如果你的二補數定義跟下面長得一樣、很操作型(?)的話啦 ============================================================= 假設有兩個人A跟B A來自alpha世界 B來自beta世界 alpha世界的人有兩隻手共十隻手指，beta世界的人同樣有兩隻手卻沒有手指兩個世界分別有 alpha算術以及 beta算術兩種系統由於手指數量的緣故，alpha算術接近地球人的十進位而beta算術比較像是地球人的二進位方便起見假設alpha算術跟beta算術的數字寫出來都是地球人的阿拉伯數字額外假設alpha世界不知道如何把bit string對應到普通alpha算術裡的數字例如看到0110這個bit string A說數字應該是像這樣吧，1 2 3 4 5 6... 10 11 12... 1000 1001... A認為0110這個東西根本不是一個alpha算術裡面該出現的數字符號因此在A看來，0110就只是一個0與1組成的字串，沒有任何alpha算術上的意義再假設「alpha算術」用的加法、等號、負號都和地球人用的一樣，分別是+=- 並假設「beta算術」的加法寫成#、等號寫成<>、負號很巧地也寫成- 經過A跟B交流後，兩人會得出一個共識 A用alpha算術寫下9+6=15 跟B用beta算術寫下1001#0110<>1111 這兩句話雖然語言不同但是指同一件事又或者A寫出(-42)+69=27 B寫出(-10 1010)#(100 0101)<>(1 1011) 這兩句話也是同一回事某天我們地球人決定教會A如何把bit string當作數字看待，甚至用bit string來算術 A說蛤 0110這種看起來根本不是alpha算術的數字啊頂多有點像B他們beta算術會出現的數字可是其實也不一樣，例如B也不會把0放在前面、寫出0110這種東西說這是個數字於是我們決定先教A所謂「二補數」是什麼二補數其實也是bit string，每個bit string都會有他對應到的二補數給定長度n的bit string v，他的二補數的作法如下: 1. 把v每個bit都翻過來，得到的結果當成u 2. 把u當作一個「beta算術」的數字，然後用beta算術的加法#來算u#1 得到結果w，也就是用beta算術來算w<>u#1 3. 把w當作一個bit string，拿右邊那n個bit出來這玩意就叫做v的二補數 A這時說好喔，反正就是拿bit string生出一個bit string嘛可是這跟數字有什麼關係? 例如他拿1111去做「二補數」得出bit string是0001 看起來還是壓根不像alpha/beta算術會出現的數字啊這時我們再告訴他，假設只考慮n bit的bit string 用二補數的方式，其實真的可以把bit string當作數字來算術 1. 對於bit string v，如果v最左邊是0 那麼把v當作一個非負alpha算術整數這個整數要是多少? 問B 也就是把v去掉多的0、然後用beta算術的角度來看待得出的那個數字就是v這個string代表的數字 2. 對於bit string v，如果v最左邊是1 把v看成一個負的alpha算術整數負多少? 先把v的二補數做出來記作u 然後問B他用beta算術看起來是多少 B說這是1，A你就把v看成(-1) B說u這玩意用你們alpha的話來講是42，A你就把v當成(-42) A明白了，反正對於bit string v，只要看他最左邊是1還是0 看情況拿原本的v、或是拿v的「二補數」u去問B A就知道這個string對應到什麼數字了「啊可是這可以幹麻，每次都問B，好煩耶」，A問「而且就算知道這些string可以當數字，我還是不知道該如何『用bit string算術』難不成我該把bit string都換成我了解的alpha數字、做alpha加法最後再想辦法換回bit string，麻煩到炸耶」「例如考慮1001+0110，問過B了、所以我知道這句bit string算術的意思用我的alpha算術來說就是求(-7)+6 這我知道答案是-1 剛好我知道1111這個bit string代表-1 所以bit string算術應該寫成1001+0110=1111 啊這是可以…」 A似乎注意到了什麼「wait… 剛剛我寫下9+6=15，B說這用beta算術寫下來是1001#110<>1111 如果我手賤、把B的算式補個0，就會寫成1001#0110<>1111 跟這個字面上好像很像? 明明其實意思根本不一樣?!」 A終於發現了，如果用「二補數」來把bit string當作普通alpha數字來計算的話寫出來跟beta算術根本87%像頂多就是多退少補、只看最右邊n個bit的事情而已 ======================================================= 好我掰不下去了總之n bit二補數剛好可以描述(-1)(2^{n-1}) ~ (2^{n-1}-1)的算術這回事我覺得是沒有這麼顯然、而且需要證明的一個證明方法當然是窮舉某個n然後歸納(n+1)的bit string也可以這樣操作不過我猜當年想出這個表示法的人應該是觀察到類似下面這個二進制算術(beta)的情況 (n+1 bit 2^n) n bit v n bit u n bit 1 10000...00000 = 0101010...100 + 1010101...011 + 0000....001 aka bit-flip version of v (n bit 0) 0000...00000 跟上面87%像看後n bit一模一樣那麼想要在n bit內做出n bit bit string v的加法反元、也就是找個w使得v+w=0 大概也就是直接抓他的bit-flip ver.、然後補上1這樣了(w := (u+1)) 方便起見把n bit bit string中MSB為0的當正數、其他當負的對應關係就用上面這個(-v) := (u+1) where u is flipped version of v 然後給這個系統掰個名字叫做2's complement ============================================================== 打到最後發現其實講最後幾句就好了… 打都打了嘖 -- ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1620774842.A.AFA.html ※ 編輯: a58524andy (118.169.36.169 臺灣), 05/12/2021 07:49:12