在学习编程的过程中，计算两个数的和
int a = b + c这样的代码肯定经常写到，但是计算机到底是怎么计算出来的呢？
加法
说到加法，首先提到的一个概念就是全加器，下图是一个全加器的数字逻辑电路。
image
其中，异或门的输出 Y = A ^ B ，与非门的输出就是先与再非，即 Y = !(A & B) 。这里我就不再列真值表了，我们再来看一下上面全加器的逻辑，通过推导可以得到下面公式：
Sum = A ^ B ^ Cin
Cout = (A ^ B & Cin) | (A & B)
这是一位（1 bit）的加法运算，当我们把 8 个全加器级联起来的话（低位的 Cout 是高位的 Cin ）就实现了一个 8 位的加法器。我们可以用代码模拟一下（LeetCode 371. 两整数之和）：
public int GetSum(int a, int b){
if(b == 0){
return a;
}
int sum, carry;
sum = a ^ b;
carry = (a & b) << 1;
return GetSum(sum, carry);
}
说到这里，大家应该大体的了解计算机是怎么计算加法的了，那减法呢？
减法
加法是进位，减法需要考虑的则是借位，是这样吗？按我们小时候对加减法学习的经验是这样的，但是计算机不是这么处理的。计算机“只有加法”，“没有减法”。肯定有同学说，不可能，那我们算 int a = b - c 是怎么得出来结果的呢？说到这个首先要了解另外一个概念——补码。
补码
我们知道，计算机中对于有符号数，用最高位作为符号位，“0” 代表 “+” ，“1” 代表 “-” ；其余数位用作数值位，代表数值。比如 Byte 类型的取值范围为 -128 ~ 127。其中，表示数值的只有 7 位，首位表示正负。
怎么推导一个数字的补码呢？补码规定，正数和 0 的补码就是其原码（原码、反码的定义这里就不多赘述），负数的补码是其正数的原码取反再加 1 。
听起来有点绕，举个例子，求 -10 的补码：
十进制 10 的原码（按 8 位举例）为 0000 1010，其反码为 1111 0101，取反后再加 1 即为其补码： 1111 0110。因此，-10 的补码为 1111 0110。
不知道写到这里，大家有没有发现什么端倪？我们再回到减法计算来。
a = b - c
实际上等同于
a = b + ( -c )
我们算一下下面的式子：
- 12 - 5
= 0000 1100 + 1111 1011
= (1)0000 0111
= 7 括号里为进位，因为只有 8 位，所以高于 8 位的进位要去掉。 - 7 - 9
= 0000 0111 + 1111 0111
= 1111 1110
= -2
通过这两个例子是不是就清楚了计算机是如何计算减法的了？
乘法
通过说减法，我们是不是对乘法也有一定的启发了呢？乘法其实就是循环的加法。比如 5 * 3 实际上就是 5 + 5 + 5。貌似就说完了。实际上不仅仅如此的。现在有一个电子器件叫做乘法器，其可以实现二进制的乘法、除法等运算。我们同样以 5 * 3 做为例子，讲解一下乘法器计算乘法的流程。
- 5 * 3 = 0000 0101 * 0000 0011
3 的第 0 位为 1 ，那么 5 左移 0 位，结果为 0000 0101 ；
3 的第 1 位为 1 ，那么 5 左移 1 位，结果为 0000 1010 ；
3 的其他高位都为 0 ，因此不再左移；
两次左移的结果累加，即 0000 0101 + 0000 1010 = 0000 1111 ，即十进制的 15 。
虽然有乘法器，但是我们发现实际的最终操作流程还是加法和位移操作计算的乘法运算。我们写的代码中的乘法到底是用乘法器算的还是转化成加法运算，我们也并不太确定，有些编译器编译的时候会对代码进行优化，会选取最优的一种算法来计算结果。
除法
除法可以通过减法来实现，比如 10 / 3 等价于 10 一直减 3 直到被减数小于 3 ，减了 3 次，那么 10 / 3 的结果就为 3 了，余数为减完剩下的值 1 。
其实上面已经提到了乘法器，除法的原理同样也类似（这里不说浮点数的除法，只说整数的除法），但是稍微复杂一点。（LeetCode 29. 两数相除）
同样我们举个例子来说明一下。
- 209 / 5 = 1101 0001 / 0000 0101
首先取 209 的最高位 1 (101 0001) 小于 101
左移一位 11 (01 0001) 小于 101
左移一位 110 (1 0001) 大于 101 ，商 1 ，余 1 (1 0001)
左移一位 11 (0001) 小于 101
左移一位 110 (001) 大于 101 ，商 1 ，余 1 (001)
左移一位 10 (01) 小于 101
左移一位 100 (1) 小于 101
左移一位 1001 大于 101 ，商 1 ，余 100
于是结果为 00101001 （41），余数为 100 （4）。
通过上面我们发现，计算机计算加减乘除，都是转换为加法和位移运算完成的，而事实上也是如此。可能我们平时编程过程中可能用不到这些内容，直接写 + - * / 就可以了，但是作为一名程序员，还是有必要了解一下计算机基础的编码以及基础的运算的。祝大家学习愉快！
转自
https://zhuanlan.zhihu.com/p/45008984
class Solution {
public int divide(int dividend, int divisor) {
boolean negitive = (dividend > 0) ^ (divisor > 0) ;//异或位负数1 相同为整数
if (divisor == 0)
return 0;
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
Long dividend1 = Math.abs(Long.valueOf(dividend));
Long divisor1 = Math.abs(Long.valueOf(divisor));
if (dividend1 < divisor1) {
return 0;
}
int h1 = 64 - Long.numberOfLeadingZeros(dividend1);
long result = 0L;
for (int i = h1-1; i >= 0; i--) {
if(dividend1>>i>=divisor1){
result += (1<<i);
dividend1 -=( divisor1<<i);
}
}
return negitive?(int)(-result):(int)result;
}
}
移位运算和加减运算的优先级
网友评论