不用加号实现两整数相加

1.减法实现

int addWithoutPlusSign(int a, int b)
{
    return a - (-b);
}

2.异或实现

对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来实现。然后考虑进位,0+0进位为0,1+0进位为0,0+1进位为0,1+1进位为1,该操作与位运算的&操作相似。

那么加法运算可以这样实现: (1)先不考虑进位,按位计算各位累加(用异或实现),得到值a; (2)然后再考虑进位,并将进位的值左移,得值b,若b为0,则a就是加法运算的结果,若b不为0,则a+b即得结果,此时可递归调用位运算函数。

具体实现:

#include <iostream>
using namespace std;

int g_fBitAdd(int a,int b)
{
        if(b==0)
            return a;
        int sum = a^b;
        int carry =(a&b)<<1;
        return g_fBitAdd(sum,carry);
}

int main()
{
        cout<<"9+1="<<g_fBitAdd(99,11)<<endl;
        cout<<"99+11="<<g_fBitAdd(99,11)<<endl;
        cout<<"-2+11="<<g_fBitAdd(-2,11)<<endl;
}

输出:

9+1=110
99+11=110
-2+11=9

计算机本质是二进制运算,许多高人和天书都展示了如何用位运算来实现让人纠结却又惊奇的事情。上面用位运算实现加法,是基于如下定理实现: 定理1:设a,b为两个二进制数,则a+b = a^b + (a&b)<<1。 **证明:**a^b是不考虑进位时加法结果。当二进制位同时为1时,才有进位,因此 (a&b)<<1是进位产生的值,称为进位补偿。将两者相加便是完整加法结果。

定理2:使用定理1可以实现只用位运算进行加法运算。 证明:利用定理1中的等式不停对自身进行迭代。每迭代一次,进位补偿右边就多一位0,因此最多需要迭代二进制数位长减一次,进位补偿就变为0,这时运算结束。

3.内嵌汇编

C/C++函数返回值是通过寄存器eax返回,所以通过内联汇编指令的方式可以实现两数相加。注意GNU C++内联汇编语法使用AT&T/UNIX语法,和Visual C++的Intel内联汇编语法不同。具体实现如下:

#include <iostream>
using namespace std;

int asmAdd(int a,int b)
{
    asm
    (
        "movl %0,%%eax\n\t"
        "movl %1,%%ecx\n\t"
        "addl %%ecx,%%eax"
        :
        :"r"(a),"r"(b)
    );
}

int main()
{
    cout<<"99+1="<<asmAdd(99,11)<<endl;
    cout<<"99+11="<<asmAdd(99,11)<<endl;
    cout<<"-2+11="<<asmAdd(-2,11)<<endl;
}

使用g++ test.cpp编译运行结果如下:

99+11=110
99+11=110
-2+11=9

关于上述内联汇编代码的有如下几点解释: (1)多行汇编指令使用\n\t进行换行,并使用双引号将单行指令括起来; (2)使用双百分号引用寄存器,告诉编译器引用的是寄存器而非操作数; (3)第一个冒号表示引用的C++的变量,用于输出,因无需输出变量,所以留空; (4)第二个冒号表示汇编代码需要读取的C++的变量,”r”表示使用任意寄存器来存放变量a和b的值,多个变量使用逗号分隔。在汇编代码中访问时,按照申请的顺序从数字0开始,使用%进行访问。比如上面代码中%0表示变量a,%1表示变量b。关于GCC的内联汇编语法,具体可以参见:GCC-Inline-Assembly-HOWTO


参考文献

[1]不用算术运算符实现两个数的加法(按位异或).CSDN [2]不用算术运算符实现两个数的加法(按位异或).博客园 [3]GCC-Inline-Assembly-HOWTO

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-204-Count Primes

2588
来自专栏iOS122-移动混合开发研究院

【读书笔记】A Swift Tour

素材:A Swift Tour 推荐下载Playground:Download Playground objc 自己较为熟悉,想熟悉下风头正劲的 swift。就...

3618
来自专栏swag code

swap()交换两个变量的方法汇总

1044
来自专栏Golang语言社区

Golang 中"泛型"的支持

Golang不支持一般的类似java中的标记式泛型。很多人因此而十分不满,认为没有泛型增加了很多工作量。而目前由于泛型支持的复杂性,Golang的设计和实现者并...

38213
来自专栏程序生活

Leetcode-Easy 796. Rotate String

796. Rotate String 描述: 有两个字符串A和B,将A的第一个字符左移到最后位置,判断此时A是否等于B,如果等于返回true。不等于则继续左...

2915
来自专栏阮一峰的网络日志

co 函数库的含义和用法

======================================== 以下是《深入掌握 ECMAScript 6 异步编程》系列文章的第三篇。 ...

3365
来自专栏数据结构与算法

177. [USACO Jan07] 有限制的素数

177. [USACO Jan07] ★   输入文件:qprime.in   输出文件:qprime.out   简单对比 时间限制:1 s   内存限制:...

3679
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict专栏)

Python3 与 C# 基础语法对比(基础知识场):https://www.cnblogs.com/dotnetcrazy/p/9102030.html

24710
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(1)

ECMAScript 6(简称ES6)是JavaScript语言的最新标准。因为当前版本的ES6是在2015年发布的,所以又称ECMAScript 2015。 ...

2295
来自专栏xingoo, 一个梦想做发明家的程序员

Oozie分布式工作流——EL表达式

oozie支持使用EL(expression language)表达式。 基本的EL常量 KB MB GB TB PB 基本EL函数 string fir...

2678

扫码关注云+社区

领取腾讯云代金券