专栏首页C/C++基础不用加号实现两整数相加

不用加号实现两整数相加

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 条评论
登录 后参与评论

相关文章

  • 网易游戏技术岗在线编程题(一)

    小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2...

    Dabelv
  • C++11就地初始化与列表初始化

    在C++11中,结构体或类的数据成员在申明时可以直接赋予一个默认值,初始化的方式有两种,一是使用等号“=”,二是使用大括号列表初始化的方式。注意,使用参考如下代...

    Dabelv
  • C的全缓冲、行缓冲和无缓冲

    基于流的操作最终会调用read或者write函数进行I/O操作。为了使程序的运行效率最高,流对象通常会提供缓冲区,以减少调用系统I/O库函数的次数。

    Dabelv
  • 每日一题C++版(合唱队)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 选择排序—简单选择排序(Simple Selection Sort)

    在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素...

    瑾诺学长
  • POJ-2752-Seek the Name, Seek the Fame

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstring> #include <vect...

    f_zyj
  • 从源代码到Runtime发生的重排序编译器重排序指令重排序内存系统重排序阻止重排序

     源代码和Runtime时执行的代码很可能不一样,这是因为编译器、处理器常常会为了追求性能对改变执行顺序。然而改变顺序执行很危险,很有可能使得运行结果和预想的不...

    用户1174983
  • POJ 刷题系列:2996. Help Me with the Game

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 2018-09-04Q:求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。方法一:递归实现1+2+..+n;

    共同点:一,利用利用短路 && 来实现 if的功能;二,利用递归来实现循环while的功能

    JavaEdge
  • “墨子号”实现1200km量子通信

    今天在arXiv看到潘建伟老师组贴出了星地量子通信的最新实验结果arXiv 1707.00542(2017)。 赶紧下载尝个鲜,先睹为快。

    光学小豆芽

扫码关注云+社区

领取腾讯云代金券