V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
netty
V2EX  ›  程序员

不用加减乘除做加法

  •  
  •   netty · 2020-02-14 21:56:27 +08:00 · 4457 次点击
    这是一个创建于 1746 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一. 十进制计算

    计算十进制 13+9:

    1.计算不进位的和。十位 1 不变,个位 3 加 9 等于 2,结果为 12 ;

    2.计算进位。十位没进位,个位进位为 1,结果为 10。

    再计算十进制 12+10:

    1.计算不进位的和。十位 1 加 1 等于 2,个位 2 加 0 等于 2,结果为 22 ;

    2.计算进位。十位没进位,个位也没进位,结果为 0。

    因此结果 13+9=22。

    二. 二进制计算

    13 二进制为:1101,9 二进制为:1001。

    十进制是遇到大于等于 10 就保留余数,然后进位 1。

    那对应到二进制,就是遇到 2 就保留余数 0,然后进位 1。(二进制位之和不可能大于 2 )

    计算二进制 1101+1001:

    1.计算不进位的和。从左到右,第 1 位为 0,第 2 位为 1,第 3 位为 0,第 4 位为 0,结果为 0100 ;

    2.计算进位。从左到右,第 1 位进位 1,第 2、3 位没有进位,第 4 位进位 1,结果为 1001。不对,进位右边要补 0,正确结果是 10010。

    计算二进制 0100+10010:

    1.计算不进位的和:10110 ;

    2.计算进位:无。

    因此结果为 10110=22。

    三.二进制加法公式

    1 )分析上面对二进制的计算过程,不难发现:

    1.计算不进位的和,相当于对两个数进制异或:1101^1001=0100 ;

    2.计算进位,第 1 位相当于对两个数求与:1101&1001=1001,然后再对其进行左移 1 位:1001<<1=10010。 然后再重复以上两个步骤。这里再异或一次就得到结果了,没进位:0100^10010=10110=22。

    2 )计算 a+b,等价于(a^b)+((a&b)<<1)。

    由于公式中又出现了+号,因此要再重复 2 )这个等价的计算过程。

    结束条件是:没有进位了。

    如果不明白,看一下前一点 1 )。

    /**
     * 二进制求和.
     * 
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b) {
        while (b != 0) {
            int plus = (a ^ b); // 求和(不计进位). 相同位置 0,相反位置 1
            b = ((a & b) << 1); // 计算进位. 先保留同为 1 的位,都为 1 的位要向左进位,因此左移 1 位
            a = plus;
        }
        return a;
    }
    
    21 条回复    2020-02-16 21:52:57 +08:00
    reself
        1
    reself  
       2020-02-14 22:29:52 +08:00 via Android
    论加法器的十八般武艺
    churchmice
        2
    churchmice  
       2020-02-15 00:11:44 +08:00 via Android
    。。。
    这就是加法器的硬件实现啊

    最后硬件就是与门,或们和非门,能帮你实现所有组合逻辑,再加上寄存器,就是你现在用的芯片
    churchmice
        3
    churchmice  
       2020-02-15 00:12:42 +08:00 via Android
    这个东西你去画下卡诺图就能推导出来了,请自行 Google
    Perry
        4
    Perry  
       2020-02-15 00:15:32 +08:00 via iPhone   ❤️ 4
    恭喜楼主喜提 ALU
    darksword21
        5
    darksword21  
       2020-02-15 00:17:13 +08:00 via iPhone
    恭喜楼主喜提 ALU
    lance6716
        6
    lance6716  
       2020-02-15 01:10:14 +08:00 via Android
    搞不懂模二加为啥被开除加法籍
    yujincheng08
        7
    yujincheng08  
       2020-02-15 01:57:36 +08:00 via Android
    恭喜楼主喜提 ALU
    leoaqr
        8
    leoaqr  
       2020-02-15 05:50:44 +08:00 via iPhone
    恭喜楼主喜提 ALU
    deepreader
        9
    deepreader  
       2020-02-15 06:30:52 +08:00
    村通网
    RtIHZ
        10
    RtIHZ  
       2020-02-15 06:47:49 +08:00
    你先定义你所说的“加减乘除”里的“加”是什么意思

    请问以下代码算实现了“加”吗?
    if (op1 == 1 && op2 == 1) {
    return 2;
    }
    msg7086
        11
    msg7086  
       2020-02-15 08:57:53 +08:00
    我以为现在上课是用的直播呢。
    slanternsw
        12
    slanternsw  
       2020-02-15 09:02:15 +08:00 via Android
    啥民科玩意儿,谔谔
    Mohanson
        13
    Mohanson  
       2020-02-15 09:06:49 +08:00 via Android
    半加器,全加器可以学一下的
    kZime
        14
    kZime  
       2020-02-15 09:07:13 +08:00 via Android
    在 v 站科普这个有点奇怪吧
    ynyounuo
        15
    ynyounuo  
       2020-02-15 09:08:42 +08:00 via iPhone
    我还以为继去年 O(n log n) 后立马又有了更快的乘法算法
    Windsooon
        16
    Windsooon  
       2020-02-15 10:04:21 +08:00
    我想大多数人误会楼主了,楼主应该了解 ALU 以及 计算机硬件如何实现加法的,楼主的想法是如何在不使用加法符号来达到加法的目的,其实在不少算法题都会有这样的要求,例如 Leetcode 29 题,这类算法题主要考察的是对位运算的理解。我觉得楼主这个想法挺有趣的,而我之前也没有想到,感谢楼主的分享。
    ZhiyuanLin
        17
    ZhiyuanLin  
       2020-02-15 13:50:39 +08:00   ❤️ 1
    应该没读过计算机相关专业,学过数字电路不会觉得这是多神奇的事情。
    xieyudi2
        18
    xieyudi2  
       2020-02-15 16:17:21 +08:00 via Android
    CPA, CSA, wallace tree...
    虽然楼主是自己想出来的可嘉,但这个真的只是学校课本上的东西…
    wi
        19
    wi  
       2020-02-15 20:17:13 +08:00
    可以的,不过这个书本上又讲
    pinktu
        20
    pinktu  
       2020-02-16 18:04:52 +08:00
    你可以做一个加法器
    lidjxy
        21
    lidjxy  
       2020-02-16 21:52:57 +08:00 via iPhone
    建议快速看一遍《 code 》,里面加法器讲的特别好
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5253 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 03:47 · PVG 11:47 · LAX 19:47 · JFK 22:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.