※ 引述《lueichun (= =)》之铭言： : : 如题，为什麽互为2的补数的两个数字，彼此一定是相反数呢？ : : 例如0101=5 那麽1011就=-5 : : 01111111=127 那麽10000001就=-127 : : 请问为什麽会这样呢？ : : -- :

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.167.40.196 (台湾) : ※ 文章网址: https://webptt.com/cn.aspx?n=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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1620774842.A.AFA.html ※ 编辑: a58524andy (118.169.36.169 台湾), 05/12/2021 07:49:12