一、题目描述
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2
二、题解
1.加法
0 1 1 1
+ 1 1 1 0
-------------
1 0 1 0 1
1+0=1
1+1=2 转为二进制 10 填0,往前进一位
1+1+1(前面进的位)=3 转为二进制 11 填1,往前进一位
0+1+1=2 转为二进制 10 填0,往前进一位
加法结果：
使用^运算(^ : 两个位相同为0，相异为1)的到的结果就是无进位相加的结果
进位信息：
如果两个都为1，那么就会有进位信息，用&运算，得到的就是1，再往左移动一位，结果就是进位信息
最终的结果就是让^运算的结果加上进位信息
得到的 ^运算结果 和 &运算结果左移 相加就是和，依次执行，直到进位信息没有了，就通过位运算实现了加法
/**
* 加法
* 0 1 1 1
* + 1 1 1 0
* -------------
* 1 0 1 0 1
*
* 1+0=1
* 1+1=2 转为二进制 10 填0,往前进一位
* 1+1+1(前面进的位)=3 转为二进制 11 填1,往前进一位
* 0+1+1=2 转为二进制 10 填0,往前进一位
*/
public int add(int a ,int b){
//相同为0，不同为1，当两个要相加的时候，相同进位为0，不同1+0=0，缺少进位信息
int result = a ^ b;
// 相同为1，不同为0；相同进位，左移一位刚好为进位信息
int carry = (a & b) << 1;
if(carry!=0){
return add(result,carry);
}
return result;
}
2.减法
1 0 1 0 0 1
- 0 1 1 0 1 0
----------------
0 0 1 1 1 1
1-0=1
0-1 不够减,往前借1(借到的是2), 2-1=1
0-0 因为被借走了一位，所以0变成-1：-1-0，不够减，往前借1，2-1-0=1
1-1 因为被借走了一位，所以1变成0：0-1，不够减，往前借1，2-1=1
0-1 因为被借走了一位，所以0变成-1，-1-1，不够减，往前借1，2-1-1=0
1-0 因为被借走了一位，所以1变成0，0-0=0
/**
* 减法
* a-b => a+(-b)
* -b => ~b+1
* @param a
* @param b
* @return
*/
public static int minus(int a, int b) {
return add(a,add(~b,1));
}
3.乘法
1 0 0 1
* 1 1 0 1
---------------------
1 0 0 1
0 0 0 0
1 0 0 1
1 0 0 1
-----------------------
1 1 1 0 1 0 1
乘法
- 当乘的位数是1的时候，还是原来的数字
- 当乘的位数是0的时候，全部是0
- 把全部的结果相加
思路：判断乘数b的位数是不是1，通过让他和1进行&运算，如果是1，说明当前位是1。（当乘数是0的时候不用考虑，因为乘出来要加的还是0）
&完的结果如果是1，把被乘数a作为要相加的和，左移一位（下一次如果是1的和）。
b右移一位，让他来到下一位去乘。
/**
* 乘法
* 1 0 0 1
* * 1 1 0 1
* ---------------------
* 1 0 0 1
* 0 0 0 0
* 1 0 0 1
* 1 0 0 1
* -----------------------
* 1 1 1 0 1 0 1
*/
public static int multiply(int a, int b) {
int lastSum = 0;
while (b != 0) {
//b和1进行&运算，判断除要乘的这位是不是1
if ((b & 1) == 1) {
lastSum = add(lastSum, a);
}
// 111
b = (b >>> 1);
a = (a << 1);
}
return lastSum;
}
4.除法
0 0 0 1 1 0 商
-------------
除数b 1 1 0 ) 1 0 0 1 1 0 被除数a
1 1 0 // 相当于b向左移动到不会超过a的位置b<=a 此位移动的次数i的位置上为1 a右移a>=b
----------- // b<<i <= a
0 0 1 1 1 // a = a-(b<<i)
1 1 0 // b向左移动到不会超过a的位置 此位商为1
------------
0 0 1 0 余数 //
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
return 1;
}
if (a != Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
return 0;
}
if (a == Integer.MIN_VALUE) {
if (b == -1) {
return Integer.MAX_VALUE;
}
/**
* 系统最小值没办法取绝对值，使用分配律解决
*
* 要计算Integer.MIN_VALUE ÷ b：
* 先计算（Integer.MIN_VALUE+1）÷ b = c
* c*b = a
* [（Integer.MIN_VALUE+1）- a] / b = d
* 商=c+d
*/
int i = divideNormal(add(a, 1), b);
int multiplyRes = multiply(i, b);
int minusRes = minus(a, multiplyRes);
int subRes = divideNormal(minusRes, b);
return add(i, subRes);
}
return divideNormal(a, b);
}
/**
* 正常除法（不包含系统最小）
* @param a
* @param b
* @return
*/
private static int divideNormal(int a, int b) {
boolean negativeA = isNegative(a);
boolean negativeB = isNegative(b);
a = negativeA ? oppositeNum(a) : a;
b = negativeB ? oppositeNum(b) : b;
int result = 0;
// int整型一共32位，一位一位的移动去尝试
for (int i = 30; i >= 0; i = minus(i, 1)) {
if ((a >> i) >= b) {
//说明第i位是1，使用|运算，让数字和1<<i去进行|运算，可以让i对应的那一位变成1。
result = result | (1 << i);
a = minus(a, b << i); //a = a-(b<<i);
}
}
return negativeA != negativeB ? oppositeNum(result) : result;
}
/**
* 判断一个数是否是负数
* @param a
* @return
*/
public static boolean isNegative(int a) {
return a < 0;
}
/**
* 取相反数
* @param a
* @return
*/
public static int oppositeNum(int a){
return ~a+1;
}
完整题解：
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) {
return 1;
}
if (dividend != Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) {
return 0;
}
if (dividend == Integer.MIN_VALUE) {
if (divisor == -1) {
return Integer.MAX_VALUE;
}
int i = divideNormal(add(dividend, 1), divisor);
int multiplyRes = multiply(i, divisor);
int minusRes = minus(dividend, multiplyRes);
int subRes = divideNormal(minusRes, divisor);
return add(i, subRes);
}
return divideNormal(dividend, divisor);
}
public int divideNormal(int dividend, int divisor) {
boolean isNegativeA = isNegative(dividend);
boolean isNegativeB = isNegative(divisor);
dividend = isNegativeA? oppositeNum(dividend):dividend;
divisor = isNegativeB? oppositeNum(divisor):divisor;
int result = 0;
for(int i=30;i>=0;i = minus(i,1)){
if(dividend>>i >= divisor){
result |= 1<<i;
//dividend = dividend - divisor<<i;
dividend = minus(dividend,divisor<<i);
}
}
return isNegativeA!=isNegativeB ? oppositeNum(result) : result;
}
public boolean isNegative(int a){
return a<0;
}
public int add(int a ,int b){
//相同为0，不同为1，当两个要相加的时候，相同进位为0，不同1+0=0，缺少进位信息
int result = a ^ b;
// 相同为1，不同为0；相同进位，左移一位刚好为进位信息
int carry = (a & b) << 1;
if(carry!=0){
return add(result,carry);
}
return result;
}
public int minus(int a,int b){
return add(a,oppositeNum(b));
}
public int multiply(int a,int b){
int result = 0;
while(b!=0){
int res = b&1;
if(res == 1){
result = add(a,result);
}
a = a<<1;
b = b>>>1;
}
return result;
}
public int oppositeNum(int a){
return add(~a,1);
}
}
网友评论