c语言中用位运算实现加法技巧介绍

用位运算实现加法也就是计算机用二进制进行运算，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)

相关推荐

  • C语言 解决不用+、-、×、÷数字运算符做加法的实现方法

    题目:写一个函数,求两个整数的之和,要求在函数体内不得使用+.-.×.÷. 分析:这又是一道考察发散思维的很有意思的题目.当我们习以为常的东西被限制使用的时候,如何突破常规去思考,就是解决这个问题的关键所在. 看到的这个题目,我的第一反应是傻眼了,四则运算都不能用,那还能用什么啊?可是问题总是要解决的,只能打开思路去思考各种可能性.首先我们可以分析人们是如何做十进制的加法的,比如是如何得出5+17=22这个结果的.实际上,我们可以分成三步的:第一步只做各位相加不进位,此时相加的结果是12(个位数

  • C语言菜鸟基础教程之加法

    先动手编写程序: #include <stdio.h> int main() { int a = 1; int b = 2; int c = a + b; printf("sum is %d\n", c); return 0; } 运行结果: sum is 3 程序分析: 先定义一个整型变量a,把1赋值给a. 再定义一个整型变量b,把2赋值给b. 最后定义一个整型变量c,它的值不是靠赋值得到的,而是把a和b相加之后的值赋值给它,即c的值为3.

  • c语言中用位运算实现加法技巧介绍

    用位运算实现加法也就是计算机用二进制进行运算,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 这样我们就完成了简单的一位数加法,那么要进行二位的加法,这个方法可行不可行呢?肯定是不行的,矛盾

  • 谈谈C语言中位运算你要知道的那些事儿

    谈谈C语言中位运算你要知道的那些事儿

    目录 一.概念说明 1.概念 1.1位运算 1.2位运算符 2.举例及补充 2.1位运算 2.2位运算符 二.问题实战 1.问题描述(开放题) 2.输入输出 三.源码实现(+详细注释) 1.注释版 2.纯源码版 四.输出结果展示 1.输出结果 总结 一.概念说明 1.概念 先来看一下位运算的概念: 1.1位运算 位运算简单来说,就是按二进制位进行运算. 位运算: 从现代计算机中所有的数据二进制的形式存储在设备中.即 0.1 两种状态,计算机对二进制数据进行的运算(+.-.*./)都是叫位运算,即

  • js中位运算的运用实例分析

    我们可能很少在编程中用位运算,如果没深入学习,可能也很难理解.平时的数值运算,其实是要先转换成二进制再进行运算的,而位运算就是直接进行二进制运算,所以位运算的执行效率肯定是更高的.下面通过一些实例来加深对位运算的理解. 按位与(&) &&运算符我们都知道,只有两个都为真,结果才为真.&道理是一样的,只有两个数的值为1时,才返回1.例如1和3的按位与操作: 0001 &  0011   ---------     0001 只有对应的数为1时,结果才为1,其他都为0.

  • Java利用位运算实现加减乘除的方法详解

    Java利用位运算实现加减乘除的方法详解

    目录 前言 一.常见位运算 1. &运算 2. |运算 3. ^运算 4. ~运算 二.位运算实现加法 三.位运算实现减法 四.位运算实现乘法 五.位运算实现除法 前言 我们经常使用的加减乘除,我们所看到的只是表面的效果,那么加减乘除在底层究竟是怎么实现的?今天就让我们一探究竟.今天用位运算实现的加减乘除不使用任何的加减乘除符号. 一.常见位运算 1. &运算 &运算二进制每一位全1为1,否则为0 public static void main(String[] args) { i

  • Java利用位运算实现加减运算详解

    目录 前言 思路分析 示例 位运算进位 初步结果 去除加号 整体思路 加法代码实现 减法实现 减法分析 减法代码实现 总结 前言 本文主要介绍如何使用位运算来实现加减功能,也就是在整个运算过程中不能出现加减符号. 加减乘除运算在计算机中,实际上都是用位运算实现的,今天就用位运算来模拟下加法和减法的运算功能. 思路分析 先分析如何用位运算实现加法运算. 示例 假设a=23,b=36,使用位运算实现加法得到结果59. 首先来看下23.36.59的二进制信息. 从上面的图中可以看到,两个数相加的结果与

  • Java利用位运算实现乘法运算详解

    目录 前言 正文 十进制相乘 二进制相乘 思路分析 代码实现 总结 前言 在上一篇中,我们介绍了使用位运算实现加法和减法运算,接下来本文主要介绍如何用位运算实现乘法运算,在实现乘法时要用位运算实现,并且不能出现加减乘除任何符号. 之前介绍过一篇如何用位运算实现加法和减法: 如何用位运算实现加减运算? 正文 在用位运算实现之前,我们先来回忆一下小学时,学乘法时用的十字相乘法. 十进制相乘 例如,26 * 15,在进行乘法操作时,我们一般这样算,先用5乘以6得到30,把0写下把3记在一边,再用5乘以

  • 如何利用C语言位运算解决只出现一次的数字

    如何利用C语言位运算解决只出现一次的数字

    解题所需要的C语言基础知识 hello!从现在开始就进入本题解的正式内容了.首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^ 这些知识对下面的解题都非常重要,一定要熟练掌握,不然等会会有一种"我在哪,我是谁我在干什么"的感觉. 只出现一次的数字I 题目描述 只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗? 示例 1:

  • 详细聊聊React源码中的位运算技巧

    目录 前言 几个常用位运算 按位与(&) 按位或(|) 按位非(-) 标记状态 优先级计算 总结 前言 这两年有不少朋友和我吐槽React源码,比如: 调度器为什么用小顶堆这种数据结构,直接用数组不行? 源码里各种单向链表.环状链表,直接用数组不行? 源码里各种位运算,有必要么? 作为业务依赖的框架,为了提升一点点运行时性能,React从不吝惜将源码写的很复杂. 在涉及状态.标记位.优先级操作的地方大量使用了位运算. 本文会讲解其中比较有代表性的部分.学到之后,当遇到类似场景时露一手,你就是业务

  • C语言位运算和sizeof运算符详解

    位运算和sizeof运算符 C语言中提供了一些运算符可以直接操作整数的位,称为位运算,因此位运算中的操作数都必须是整型的.位运算的效率是比较高的,而且位运算运用好的话会达到意想不到的效果.位运算主要有6种:与(&),或(|),取反(~),异或(^),左移(<<),右移(>>). 1.位运算中的类型转换 位运算都必须进行Integer Promotion.在进行运算之前,都必须将char型.short型的数据转换为int或者unsigned int型再参与运算. 如下面这段程

  • 图文详解C语言位运算基础知识

    图文详解C语言位运算基础知识

    C语言位运算基础知识分享给大家,希望对大家有帮助. 1.   程序中的所有数在计算机内存中都是以二进制的形式储存的.位运算说穿了,就是直接对整数在内存中的二进制位进行操作. 2.  与运算:只有前后两个运算数都是 1 的时候结果才是1. 3.  或运算:有1位为1,结果便为1. 4.  异或:不相同则为1. 5.  取反运算:将1变为0,将0变为1. 6.  移位运算:左移则乘2,右移则除2.如果超出边界,则舍弃. 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们.

随机推荐