当我们没有加减乘除之后
这周刷题恰巧遇到了几个有意思的题目，有一道题脑洞大开，分享出来给大家欣赏一下哈~
两个整数相加
T371---两个整数相加【简单题】 题目描述
题目描述
简单而言，就是当我们无法使用+和-的时候，我们该如何计算两个数的加法。
1、解决思路
当我们看到无法使用加法和减法的时候，我们的第一印象应该就是想着转化思维，去思考计算机的底层到底是什么运算呢？
其实我们都很清楚，在计算机的底层都是0和1的比特进行与或非的操作运算。那么我们先来看看两个位加法的底层是什么样子的。
两个数的位运算
只有下面的4种情况。
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 （无进位）
1 + 1 = 10 （有进位）
观察上面的4种情况。如果我们去掉有进位的情况，那么所有的无进位加法，就是异或操作的结果。所以我们可以先考虑无符号的异或操作，计算加法。然后再计算进位部分。
那么进位部分该怎么处理呢？此时我们可以看一个案例
a = 2 0010
b = 3 0011
无进位，异或操作
0010
0011
----
0001
进位符，与操作
0010
0011
----
0010
当与操作之后，我们可以得到进位符，但是直接得到的结果并不是我们需要的进位结果。需要将与操作后的结果左移1个单位，此时每一个进位的数字，就在合适的位置啦~
算法归纳
- 将两个数进行异或操作，得到无进位加法的结果。
- 将两个数进行与操作，并左移一位，得到进位符。
- 将进位符与无进位加法结果重复上面的两步。直到进位符为0。
2、代码实现
public int getSum(int a, int b) {
int sum = a ^ b; //无符号加法，异或操作
int carry = (a & b)<<1; //计算a和b的进位，与操作
while(carry != 0){
int temp = sum^carry; //计算无符号结果和进位之间的加法，异或操作
carry = (sum&carry)<<1; //计算sum和carry的进位，与操作
sum = temp;
}
return sum;
}
一顿操作之后，才能感受到我们习以为常的加法有多么的伟大。嘻嘻，算不算平凡中的伟大呢？来继续看看下面的除法吧！
两数相除
T29---两个整数相加【中等题】 题目描述
题目描述
题目要求也很明确，不允许使用乘法和除法，来完成除法。
1、解决思路
这道题不允许我们使用乘法和除法，但是还可以使用加减法的。所以，第一印象可能就是将其转换为加减法，循环的加减，直到余数小于除数。
于是我们就可以开工了，但是其中有几个细节需要注意一下。
处理细节
- 题目中已经明确给出了int类型的溢出问题。所以这是我们首要考虑的。
- 为了避免在处理的过程中来回切换正负号的问题，我们可以尝试着将所有的除数与被除数都转换为正数。
- 在我们正负转换之间，由于正数的范围和负数的范围不同，所以为了转换过程中出现失真。我们可以换一种数据类型，使用long类型来接受转换后的数据。
- 在进行减法操作的时候，我们可以试着使用一下倍增和移位操作，来加速我们快速找到最后的结果。
2、代码实现
public int divide(int dividend, int divisor) {
//处理溢出
if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
if(divisor == 1)return dividend;
boolean flag = false;//标识符号位
boolean min = false;//被除数是最小值
long dividend1 = (long)dividend;
long divisor1 = (long)divisor;
//将除数和被除数都转换为正数
if(dividend < 0){
dividend1 = 0 - dividend1;
flag = !flag;
}
if(divisor < 0){
divisor1 = 0 - divisor1;
flag = !flag;
}
long q = divisor1;//减数
long ans = 0;
long count = 1;//每次增加的数量
while(dividend1 >= divisor1){
if(q < dividend1){
dividend1 -= q;
ans += count;
q += q;//对减数进行翻倍
count += count;//每次加3的个数也进行翻倍
}else if(q == dividend1){
ans += count;
break;
}else{
q = q>>1;
count = count >> 1;
}
}
return (int)(flag?0-ans:ans);
}
简单的操作，我们又完成了一步创举。下面看看本次的压轴题目，会让你觉得，不枉来世界上走一遭~
3的幂
T326---3的幂【简单题】 题目描述
题目描述
给定一个整数，判断是否是3的幂。
1、解决思路
这道题可以使用乘除法了，有没有有点小开心。哈哈！
首要的思路或许就是一路循环到底，将给定的整数不断的对3取模是否等于0，然后除以3，不断的重复下去。这应该是比较好理解的态度了吧！
但是当我们介绍下面的思路的时候，或许你会眼前一亮~
数学中有基本的换底公式
如果n为3的幂，那么就有n = 3^i，那么i = log3(n)并且i为整数。所以我们可以逆向推导，i = log3(n) = log10(n)/log10(3),如果我们计算得到的i为整数，那么便可以得知n为3的幂。
操作细节
- 由于在计算对数过程中，会出现小数点的情况。所以我们需要注意接收对数结果的数据类型。
2、代码实现
public boolean isPowerOfThree(int n) {
double res = Math.log10(n)/Math.log10(3);
return res-(int)res == 0 ? true:false;
}
这道题的解法有没有让你眼前一亮呢~嘻嘻,还是很奇妙的吧！