为什么位运算可以实现加法

- 日理万妓 2023-03-12 09:28 21阅读 0赞

# 总结 #

**1、 不考虑进位的情况下位运算符中的异或^可以表示+号**

**2、 位运算符中的与运算符&和左移运算符<<可以模拟加法中的进位**

**3、位运算不仅可以做加法，还可以做其它的乘法减法等：计算机本质是二进制运算，许多高人和天书都展示了如何用位运算来实现让人纠结却又惊奇的事情。（所以位运算是可以实现加减乘除的）**

# 为什么位运算可以实现加法 #

用位运算实现加法也就是计算机用二进制进行运算，32位的CPU只能表示32位内的数，这里先用1位数的加法来进行，在不考虑进位的基础上，如下

1 + 1 = 0  
1 + 0 = 1  
0 + 1 = 1  
0 + 0 = 0

很明显这几个表达式可以用位运算的“ ^ ”来代替（不考虑进位的情况下位运算符中的异或^可以表示+号），如下

1 ^ 1 = 0  
1 ^ 0 = 1  
0 ^ 1 = 1  
0 ^ 0 = 0

这样我们就完成了简单的一位数加法，那么要进行二位的加法，这个方法可行不可行呢？肯定是不行的，矛盾就在于，如何去  
获取进位？要获取进位我们可以如下思考：

0 + 0 = 0  
1 + 0 = 0  
0 + 1 = 0  
1 + 1 = 1

//换个角度看就是这样

0 & 0 = 不进位  
1 & 0 = 不进位  
0 & 1 = 不进位  
1 & 1 = 进位

正好，在位运算中，我们用“<<”表示向左移动一位，也就是“进位”。那么我们就可以得到如下的表达式

(x&y)<<1

到这里，我们基本上拥有了这样两个表达式

x^y //执行加法
    (x&y)<<1 //进位操作

我们来做个2位数的加法，在不考虑进位的情况下

11+01 = 100  // 本来的算法

用推算的表达式计算

11 ^ 01 = 10 
    (11 & 01) << 1 = 10

到这里 我们用普通的加法去运算这两个数的时候就可以得到 10 + 10 = 100

但是我们不需要加法，所以要想别的方法，如果让两个数再按刚才的算法计算一次呢

10 ^ 10 = 00

(10 & 10) << 1 = 100

到这里基本上就得出结论了，其实后面的那个 “00” 已经不用再去计算了，因为第一个表达式就已经算出了结果。

继续推理可以得出三位数的加法只需重复的计算三次得到第一个表达式的值就是计算出来的结果。

c代码如下：

int Add(int a,int b)
    {
        
     int jw=a&b;
     int jg=a^b;
     while(jw)
     {
        
      int t_a=jg;
      int t_b=jw<<1;
      jw=t_a&t_b;
      jg=t_a^t_b;
     }
     return jg;
    }

计算机本质是二进制运算，许多高人和天书都展示了如何用位运算来实现让人纠结却又惊奇的事情。在豆瓣上看到一篇日志描述如何用位运算实现乘法，其实问题解决的关键是如何用位运算实现加法。觉得原文叙述不够精确，现总结如下。

*  定理1：设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。  
    证明：a^b是不考虑进位时加法结果。当二进制位同时为1时，才有进位，因此 (a&b)<<1是进位产生的值，称为进位补偿。将两者相加便是完整加法结果。
 *  定理2：使用定理1可以实现只用位运算进行加法运算。  
    证明：利用定理1中的等式不停对自身进行迭代。每迭代一次，进位补偿右边就多一位0，因此最多需要加数二进制位长度次迭代，进位补偿就变为0，这时运算结束。

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关为什么位运算可以实现加法

总结 1、不考虑进位的情况下位运算符中的异或^可以表示+号 2、位运算符中的与运算符&和左移运算符<<可以模拟加法中的进位 3、位运算不仅可以做加法，还可以做其它

- 日理万妓/ 2023年03月12日 09:28/ 0 赞/ 22 阅读

相关位运算可以实现哪些功能

位运算可以实现哪些功能许多时候，我们为了减少算法的时间复杂度，都是推荐使用位运算，今天我们整理一下位运算可以实现哪些功能。 1. 乘除2 左

ゝ一世哀愁。/ 2022年08月06日 15:03/ 0 赞/ 113 阅读

相关加密可以这样简单（位运算）

通过位运算的“^”异或运算符把字符串与一个指定的值进行异或运算，从而改变字符串每个字符的值，这样就可以得到一个加密后的字符串。当把加密后的字符串作为程序输入内容，异或

女爷i/ 2022年07月11日 10:30/ 0 赞/ 130 阅读

相关 Java用位运算计算加法

package com.nightliar; public class Test { public static void main(Str

「爱情、让人受尽委屈。」/ 2022年06月18日 03:56/ 0 赞/ 206 阅读

相关用位操作实现加法运算

问题描述：对下面代码中的a进行位操作（只能进行位运算），实现输出OPQ int a = 0x434241; printf("%s\n", (char)&

不念不忘少年蓝@/ 2022年06月15日 23:08/ 0 赞/ 203 阅读

相关 java_位运算加法_8位二进制

package algorithm; import java.util.Scanner; /\\将二进制字符串转为int 例如00000111转化成int 7而不是

冷不防/ 2022年06月13日 03:18/ 0 赞/ 249 阅读

相关 ARM指令--adc 实现64位加法运算

今天刚刚接触到ARM指令，对于adc指令的理解，用adc指令实现64位的加法运算。 (1)adc指令:带进位的加法 (2)基本思路:(r0,r1) = (r0,r1) +

爱被打了一巴掌/ 2022年05月29日 07:19/ 0 赞/ 287 阅读

相关大数加法运算

// 大数加法运算 include <stdio.h> include <stdlib.h> include <string.h>

心已赠人/ 2022年05月28日 02:23/ 0 赞/ 224 阅读

相关加密可以这样简单（位运算）

通过位运算的“^”异或运算符把字符串与一个指定的值进行异或运算，从而改变字符串每个字符的值，这样就可以得到一个加密后的字符串。当把加密后的字符串作为程序输入内容，异或运算会

墨蓝/ 2022年04月11日 12:43/ 0 赞/ 133 阅读

相关 js加法运算

1：首先JS是一种弱语言，但是同类型可以自己相加减例如“a”+”b” 可以自动组成ab ； 1+ 2 自动变成3 var data = 2; v

客官°小女子只卖身不卖艺/ 2022年03月25日 11:42/ 0 赞/ 214 阅读