位运算加法

leetcode 面试题 17.01. 不必加号的加法

1. 运算符号

2. 运算阐明

2.1 与运算 &

and 运算通常用于二进制的取位操作，例如一个数 & 1 的后果就是取二进制的最末位。这能够用来判断一个整数的奇偶，二进制的最末位为 0 示意该数为偶数，最末位为 1 示意该数为奇数。

雷同位的两个数字都为 1，则为 1；若有一个不为 1，则为 0。

00101  
11100  
00101&11100  // 00100

2.2 或运算 |

or 运算通常用于二进制特定位上的无条件赋值，例如一个数 | 1 的后果就是把二进制最末位强行变成 1。如果须要把二进制最末位变成 0，对这个数 or 1 之后再减一就能够了，其实际意义就是把这个数强行变成最靠近的偶数。

雷同位只有一个为 1 即为 1。

00101  
11100  
00101|11100  // 11101

2.3 异或运算 ^

异或的符号是 ^。按位异或运算, 对等长二进制模式按位或二进制数的每一位执行逻辑按位异或操作. 操作的后果是如果某位不同则该位为 1, 否则该位为 0.
异或运算的逆运算是它自身，也就是说两次异或同一个数最初后果不变，即（a ^ b) ^ b = a。xor 运算能够用于简略的加密，比方我想对我 MM 说 1314520，但怕他人晓得，于是单方约定拿我的生日 19880516 作为密钥。1314520 xor 19880516 = 20665500，我就把 20665500 通知 MM。MM 再次计算 20665500 xor 19880516 的值，失去 1314520，于是她就明确了我的希图。

雷同位不同则为 1，雷同则为 0。

00101
11100
00101^11100  // 11001

2.4 按位取反 ~

取反的符号是~, 按位取反运算, 就是取数值的反码. 具体例子如下：

let num1 = 3;    // 我的侥幸数字是 3
let num2 = ~(num1);
console.log(num2)  //  "-4"
let num3 = -3;  
let num4 = ~(num3);
console.log(num4)  //  "2"
console.log(~(0))  //  "-1"

二进制负值的计算是除去符号位的数值取反再加 1.
具体的计算请先相熟原码、补码、反码之间的关系。

2.5 按位左移 <<

取反的符号是 <<，这个操作符会将数值的所有位向左挪动指定的位数。在左移后，原数值右侧空出的位由 0 填补。

左移一位其实就相当于将原数值乘以 2，左移不会影响操作数的符号位。

let a = 100;
a<<2 // 400

2.6 按位右移 >>

取反的符号是 >>，这个操作符会将数值向右挪动，但保留符号位。在移位过程中，空缺位呈现在原数值的左侧，符号位的右侧，用符号位的值来填充空位。

右移一位相当于原数除 2 后向下取整。

let a = 100;
a>>2 // 25

let b = 101;
b>>2 // 25

3. 位运算实现加法

用位运算实现加法也就是计算机用二进制进行运算。首先咱们来实现用 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

这样咱们就实现了一位数的运算，那是不是也能够这样进行 2 位数的运算呢？这是不能够的, 问题在于怎么去进位。

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”曾经不必再去计算了，因为第一个表达式就曾经算出了后果。
通过推理能够得出三位数的加法只需反复的计算三次失去第一个表达式的值就是计算出来的后果。

js 代码
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    // return a+b;
    let ab_yu = a&b;
    let ab_yihuo = a^b;
    
    while(ab_yu){
        let e = ab_yihuo;
        let f = ab_yu<<1;
        ab_yu = e&f;
        ab_yihuo = e^f;
    }
    
    return ab_yihuo;
};

4. 位运算加法论断

论断 1：设 a，b 为两个二进制数，则 a +b = a^b + (a&b)<<1。
证实：a^b 是不思考进位时加法后果。当二进制位同时为 1 时，才有进位，因而 (a&b)<<1 是进位产生的值，称为进位弥补。将两者相加便是残缺加法后果。

论断 2：应用论断 1 能够实现只用位运算进行加法运算。
证实：利用定理 1 中的等式不停对本身进行迭代。每迭代一次，进位弥补左边就多一位 0，因而最多须要加数二进制位长度次迭代，进位弥补就变为 0，这时运算完结。