29. 两数相除
29. 两数相除
题目描述
给定两个整数，被除数 dividend和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数dividend 除以除数divisor得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2
解题思路1
别天真，就用除法就完事了！！但是，，注意溢出。。
int divide(int dividend, int divisor){ //溢出判断 if(dividend == -2147483648 && divisor == -1) return 2147483647; return dividend/divisor; }
解题思路2
首先处理溢出的情况，和一些特殊情况。然后中间利用乘法的快速加实现来做判断。建议以后再看，过于难了
int MIN_INT = -2147483648; //int的最小值 int MAX_INT = 2147483647; bool quickadd(int y, int z, int x){ //判断z*y >= x? int result = 0,add = y; while(z){ if(z & 1){ if(result < x - add) return false;//保证 result + add >= x result += add; } if(z != 1){ if(add < x - add) return false; // 保证add + add >= x add += add; } z >>= 1; } return true; } int divide(int dividend, int divisor){ //异常处理 if(dividend == MIN_INT) //被除数的溢出处理 if(divisor == -1) return -(MIN_INT + 1);//超出正整数表示范围 返回2^31-1 else if(divisor == 1) return MIN_INT; //除1直接返回相应的值 if(divisor == MIN_INT) //除数的溢出处理 if(dividend == MIN_INT) return 1; //两个想等的数字相除 返回1 else return 0; //其它情况都是返回0 的 int flag = 0;//记录正负 if(dividend > 0) dividend = -dividend,flag++;//统一处理为负数 if(divisor > 0) divisor = -divisor,flag ++; //统一处理为负数 int a = 0,b = MAX_INT,ans = 0; //定义左右点和结果 while(a <= b){ int mid = a + ((b - a) >> 1); if(quickadd(divisor,mid,dividend)){ printf("d"); ans = mid; if(mid == MAX_INT) break; a = mid + 1; } else b = mid -1; } return flag & 1 ? -ans :ans; }
50. Pow(x, n)
50. Pow(x, n)
题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
解题思路1
别天真，就用pow就完事了！！
double myPow(double x, int n){ return pow(x,n); }
解题思路2
是利用二分快速幂的思想。建议以后再看，过于难了
double myPow(double x, int n){ double ans = 1; unsigned int m = n; if(n < 0) m = -(unsigned)n,x = 1.0 /x; while(m){ if(m&1) ans *= x; m>>=1; x*=x; } return ans; }
69. Sqrt(x)
69. Sqrt(x)
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
解题思路1
别天真，就用sqrt就完事了！！
int mySqrt(int x){ return sqrt(x); }
解题思路2
利用二分的思想，去找到一个最小的能达到mid*mid < x的值。
int mySqrt(int x){ int left = 0,right = ((unsigned)1<<16); while(left < right){ unsigned mid = left + ((right - left) >> 1); if(mid * mid > x) right = mid; else if(mid * mid < x) left = mid + 1; else return mid; } return left - 1; }
面试题 16.07. 最大数值
面试题 16.07. 最大数值
题目描述
编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。
解题思路1
别天真，就用fmax就完事了！！
int maximum(int a, int b){ return fmax(a,b); }
解题思路2
利用加减法判断正负号。为了防止溢出采用long long，然后右移可以移动符号位，移动63位就刚好可以移动变为0或者-1。然后+1就可以变为1和0。然后变成a和b就好了。
int maximum(int a, int b){ long long c = (long long) a - (long long)b; c >>= 63; c += 1; return a*c + b*(!c); }
