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

不用加减乘除做加法

  •  
  •   netty · 175 天前 · 3268 次点击
    这是一个创建于 175 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一. 十进制计算

    计算十进制 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   175 天前 via Android
    论加法器的十八般武艺
    churchmice
        2
    churchmice   175 天前 via Android
    。。。
    这就是加法器的硬件实现啊

    最后硬件就是与门,或们和非门,能帮你实现所有组合逻辑,再加上寄存器,就是你现在用的芯片
    churchmice
        3
    churchmice   175 天前 via Android
    这个东西你去画下卡诺图就能推导出来了,请自行 Google
    Perry
        4
    Perry   175 天前 via iPhone   ❤️ 4
    恭喜楼主喜提 ALU
    darksword21
        5
    darksword21   175 天前 via iPhone
    恭喜楼主喜提 ALU
    lance6716
        6
    lance6716   175 天前 via Android
    搞不懂模二加为啥被开除加法籍
    yujincheng08
        7
    yujincheng08   175 天前 via Android
    恭喜楼主喜提 ALU
    leoaqr
        8
    leoaqr   174 天前 via iPhone
    恭喜楼主喜提 ALU
    deepreader
        9
    deepreader   174 天前
    村通网
    RtIHZ
        10
    RtIHZ   174 天前
    你先定义你所说的“加减乘除”里的“加”是什么意思

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