Divide two integers without using multiplication, division and mod operator.
A:
18年最新一遍。 思路是： 递归调用，然后核心在最后3行。
class Solution {
public:
int divide(int dividend, int divisor) {
if( divisor == 0 || (dividend == INT_MIN && divisor == -1) ){
return INT_MAX;
}
int sign = 1;
if( (dividend > 0 && divisor < 0) || (dividend <0 && divisor > 0)) {
sign = -1;
}
if( dividend > 0){
dividend = - dividend;
}
if (divisor > 0){
divisor = - divisor;
}
int res = helper(dividend, divisor);
return sign > 0? res: -res;
}
int helper(int& a , int b){// a<0 and b < 0
if(a>b){
return 0;
}else if(a -b > b ){
a -= b;
return 1;
}else{ // a <= 2*b
int res = helper(a, b+b); // this time, delete the top result
res += res;
return res + helper(a,b); // recall this result
}
}
};
一上来， 还是按照了老的思路--------------哎，Tiger，你白白地搞了第一遍啊， 没有学到东西啊----------------这里，我还是用了学的思路， 做两两对比，然后做减法 ---------------
public class Solution {
public int divide(int dividend, int divisor) {
assert(divisor != 0): "divisor cannot be zero";
long a = dividend, b = divisor;
int sign = -1;
if( (a>=0 && b >0) || ( a<0 && b<0) ) // if both positive or negative
sign = 1;
if(a<0) a = -a;
if(b<0) b = -b;
b = b<<31;
int result = 0;
for(int i =0;i<=31;i++){
int tmp = 0;
if(a>=b ){
tmp = 1;
a -= b;
}
b = b>>1;// shift first, assume the case 1 / 1
result = ( result<<1 ) + tmp;
}
return result*sign;
}
}
Error:
1: after chaning a --> aa(long) and b--> bb(long), but in the while loop, we forget to use aa and bb .
2: 不管a b的大小关系如何，都要先把结果移位后，再加1或者加0.
3: when result == 0, tmp == 1, what is the result of the following code ???
result = result<<1 + tmp; (see the end of this page)
4: divisor = -2147483648, when ， fuck， 问题处在这里。 原本现搞成int a, b, 再转换正负号。然后再转换成long类型。
后来，直接转换成long类型，没有先判断正负号。 导致b <<32之后，变成负的了。
哦，不是这个问题， 问题是这样：
divisor = -2147483648
divisor = Math.abs(divisor); 的结果，会是什么呢？？？？？（见本页最后）
********************************************************************
思路就是，按照手算的过程， 写入----------------------搞了TMD一个晚上，Tiger，你行不行啊？？？ 磨磨蹭蹭， 犹犹豫豫，婆婆妈妈，不是男人！！！！！！肏！！！！
public class DivideTwoIntegers {
public int divide(int dividend, int divisor) {
// Use the way, just like hand-written
assert (divisor != 0);
// get sign
long longDividend = dividend;
long longDivisor = divisor;
int sign = 1;
if ((longDividend < 0 && longDivisor > 0) || (longDividend > 0 && longDivisor < 0)) {
sign = -1;
}
if (longDividend < 0) { // get inverse and add 1
long tmp = ~longDividend;
longDividend = tmp + 1;
}
if (longDivisor < 0) { // get inverse and add 1
long tmp = ~longDivisor;
longDivisor = tmp + 1;
}
// NOW, both divisor and dividend are non-negative
// and the 31th bits are both zero
// find the i_{th} shift that would make divisor > dividend
int nLeftShift = 0;
while (longDivisor <= longDividend ) {
longDivisor = longDivisor << 1;
nLeftShift++;
}
int result = 0;
longDivisor = longDivisor >> 1; // now divisor is less than zero
nLeftShift--;
// following while loop is the hand written step
for (int i = nLeftShift; i >= 0; i--) {
if (longDividend >= longDivisor) {
result += 1 << i;
longDividend -= longDivisor;
}
longDivisor = longDivisor >> 1;
}
if (sign < 0) {
result = -result;
}
return result;
}
}
Mistakes:
1： 第一遍是思路不对，用了复杂的数据结构来存储临时的2的次幂。
2： 第二遍呢， 是自己知道，手动怎么做，但是，缺傻了吧唧的， 磨磨蹭蹭，头脑不清醒，不知道怎么做。
3： 最后，还是在网上找了简介，重新学习了， 怎么用手去做除法， TNND。 时间就是生命啊， Tiger
4: 在编程的时候，没有检测，当 二者相等的时候， 也是商1 的。
即： if(dividend >= divisor){ 这里要有等号。
5: 当输入相等的时候， 结果是0 ， ？？？？？？？
原因在于，开始的时候，头脑不清醒。
当寻找nLeftShift以使之大于 dividend ， 以备后面右移一位。 应该加上 相等的条件。
while (divisor <= dividend && nLeftShift < 31) {
divisor = divisor << 1;
nLeftShift++;
}
6: 情况考虑的不周。 有可能是已经divisor用力左移，也无法比dividend大。 这个时候，是可以达到nLeftDividend = 31的。
7: 对于 int 类型的最小数 -2147483648， 将之取反加一之后，还是这个数儿啊。 郁闷~~~
为解决这个问题，我们将int 类型，改成long类型。 哎，都是泪啊~~~
（--------由于扩充了范围，就不存在右移divisor ，却不能大于dividend的问题了）
----------------第二遍-------------------------
8: result << 1 + curResult; 这样一句，是先计算 加法，再计算 移位。 哎~~~~~~~~~~
9 ：
for (int i = 0; i <= nShift; i++) { 这里，应该是<= 符号的， 自己仔细想想吧。 Tiger
Learned:
比如在十进制中，从十位借一位到个位，用在个位减的时候，就是10+个位上的数，二进制，从十位借一位到个位，用在个位减的时候，就是2+个位上的数
比如说：101-11，个位够减，为0，十位不够，从百位上借1，所以十位就为2，被减数十位-减数十位，为2-1=1，所以结果为10
如果是定点数（整数），那就舍掉了。
如果是浮点数，则继续加位运算，直到精度达到后舍掉。
二进制的乘法远比十进制简单，比如乘数是1011，只需将将被乘数分别左移3位、1位，移动后补入0，并将这三个数（被乘数左移3位的、被乘数左移1位的及未移位的被乘数）在累加器中相加，所得总和就是积，根据需要积可再转化为十进制。
除法与乘法类似，只不过将左移改为右移，加改成减。实际上减也是通过取补码后再加
除法一般不好优化，直接按照笔算步骤来算就可以了：
1、根据被除数（余数）和除数的大小来上商；
2、被除数（余数）低位补0，再减去右移后的除数，也可以改为左移余数，减去除数，这样可以确保参与运算的寄存器具有相同的位数；
3、商写到寄存器的最低位，然后商左移1位。
连续做减法，现在公认的就是这个，让被除数连续减去n个除数，直到差小于除数时为止，这样减去的次数就是商，剩下的差就是余数。
--------------------第二遍-----------------------思路同上， 只不过是for循环更改了-----------
public class Solution {
public int divide(int dividend, int divisor) {
long a = dividend; // in case overflow for negative input
long b = divisor;
int sign = 1;
if ((a < 0 && b > 0) || a > 0 && b < 0)
sign = -1;
if (a < 0)
a = -a;
if (b < 0)
b = -b;
if (b == 0)
if (sign == 1)
return Integer.MAX_VALUE;
else
return Integer.MIN_VALUE;
int nShift = 0;
while (a >= b) {
b = b << 1;
nShift++;
}
b = b >> 1;
nShift--;
// now b is right less than a
int result = 0;
for (int i = 0; i <= nShift; i++) {
int curResult = 0;
if (a >= b){
curResult = 1;
a -= b;
}
b = b >> 1;
result = (result << 1 ) + curResult;
}
if (sign > 0)
return result;
else
return -result;
}
}
------------------下面的做法， 会memory limit exceed ---------
public class Solution {
public int divide(int dividend, int divisor) {
// using two time of the divisor,
int a = dividend;
int b = divisor;
int sign = 1;
if( a<0 && b<0 ){
a = -a;
b = -b;
}else if( a>0 && b <0 ){
b = -b;
sign = -1;
}else if ( a<0 && b>0 ){
a=-a;
sign = -1;
} // else both are positive
if(b == 0)
return Integer.MAX_VALUE;
// use to build list to use DP
ArrayList<Integer> al = new ArrayList<Integer>();
int doubledValue = b;
while(doubledValue < a ){
al.add(doubledValue);
doubledValue += doubledValue;
}
al.add(Integer.MAX_VALUE);// add max value to avoid end testing
if(sign >0 )
return getDivide(a,b,al);
else
return 0 - getDivide(a,b,al);
}
private int getDivide(int a, int b , ArrayList<Integer> al){
// both a and b are positive
if(a<b)
return 0;
int powerof2 = 1;
int i=1;
for( i =1;i< al.size();i++ ){
if( al.get(i) > a ){
break;
}else{
powerof2 += powerof2;
}
}
return powerof2 + getDivide(a - al.get(i-1) ,b,al);
}
}
*****************************************************answer:
1：
when result == 0, tmp == 1, what is the result of the following code ???
result = result<<1 + tmp; (see the end of this page)
==> 0
因为 加法的优先级比移位高
2:
divisor = -2147483648
divisor = Math.abs(divisor); 的结果 --> divisor保持不变。
因为，
int k = -2147483648;
System.out.println(Integer.toBinaryString(k));
会打印： 10000000000000000000000000000000
No comments:
Post a Comment