没有使用“/”的分区
任何人都可以告诉我一个有效的方法来执行除法操作，而不使用“/”。 我可以使用类似二进制search的方法来计算log(n)步骤中的整数值。
115/3 57 * 3 > 115 28 * 3 < 115 47 * 3 > 115 . . . 38 * 3 is quotient value .....
但是还有其他更有效的方法吗？
典型的方法是移位和减去。 这与我们在学校学到的长分区基本相似。 最大的区别在于，在小数点中，您需要估计结果的下一个数字。 在二进制中，这是微不足道的。 下一个数字总是为0或1.如果（左移）除数小于或等于当前的除数值，则减去它，结果的当前位是1.如果它更大，那么当前位的结果是0.代码如下所示：
unsigned divide(unsigned dividend, unsigned divisor) { unsigned denom=divisor; unsigned current = 1; unsigned answer=0; if ( denom > dividend) return 0; if ( denom == dividend) return 1; while (denom <= dividend) { denom <<= 1; current <<= 1; } denom >>= 1; current >>= 1; while (current!=0) { if ( dividend >= denom) { dividend -= denom; answer |= current; } current >>= 1; denom >>= 1; } return answer; }
这与我们长时间分手的情况非常相似。 例如，我们来考虑972/5。 在十进制长分区，我们做这样的事情：
____ 5)972
然后我们逐个数字。 5进入9次，所以我们在答案的那个数字中写下1，从分数的那个数字中减去1 * 5，然后“下降”分配的下一个数字：
1 ---- 5)972 5 --- 47
我们继续这样做，直到我们填入所有的数字：
194 ---- 5)972 5 --- 47 45 --- 22 20 --- 2
所以，我们的答案是194剩余2。
现在让我们考虑同样的事情，但在二进制。 二进制中的972是11 1100 1100 ，而5是101 。 现在在二进制和十进制之间做一个基本的区别：在十进制中，一个特定的数字可以是从0到9的任何值，所以我们不得不乘以find我们要从被除数中减去的中间结果。 在二进制中，数字只会是0或1.我们不需要乘法，因为我们只会乘以0或1（我们通常在if语句中处理 – 要么减去要么我们不）。
----------- 101)1111001100
所以，我们的第一步是找出结果中的第一个数字。 我们通过比较101到1111001100来做到这一点，并将其左移，直到更大。 这给了我们：
| 1111001100 10100000000
当我们这样做的时候，我们会计算我们已经移动的地方的数量，所以我们知道在任何给定的时间里我们填写的结果是哪个数字。 我已经用上面的竖条显示了。 然后，我们将中间结果右移一个位置，然后将垂直条向右移动，以表示我们正在填充结果数字的位置：
| 1111001100 1010000000
从那里我们检查移位的除数是否低于股息。 如果是这样，我们在答案的正确位置填上1，从中间结果中减去移位的除数[并且为了保持列的直线，我将插入一些空格]：
1 ----------------------------- 101)1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 ---------------------------- 1 0 1
我们继续以相同的方式填充结果的数字，并从中间结果中减去移位的除数，直到我们填入所有的数字。 在进一步尝试帮助保持直线时，我将在减数中最右边的结果的每个数字中写入：
1 1 0 0 0 0 1 0 ----------------------------- 101)1 1 1 1 0 0 1 1 0 0 1 0 1 1 ----------------------------- 1 0 1 1 0 1 1 ----------------------------- 0 0 0 0 -------------------------- 0 0 0 0 ------------------------- 0 0 1 0 ------------------------- 0 1 1 0 ------------------------- 1 1 0 1 0 1 1 ------------------------ 0 1 0 0
因此，我们得到了11000010的结果，余数为10.将它们转换为十进制，我们分别得到了预期的194和2。
让我们考虑一下如何与上面的代码相关联。 我们首先将剩余因子移到比分红更大的位置。 然后我们重复右移，每次右移检查这个值是否小于最后一次减法后的中间值。 如果更less，我们再次减去，并在结果中填入1 。 如果更大，我们“减去0”（不要做任何事情），并在结果中填入一个“0”（这又不要求我们做任何事情，因为这些数字已经设置为0的）。
当我们填入所有数字时，这就是我们的结果，剩下的还没有减去的数字就是我们的余数。
有人问我为什么在代码中使用|=而不是+= 。 我希望这有助于解释为什么。 虽然在这种情况下他们产生相同的结果，我不认为增加每个数字到现有的部分答案。 相反，我认为这个答案是空的，而且正好填补了这个空白。
选项：
- 根据您在小学所学的长分类algorithm，编写您自己的分区algorithm。
- 取分母的-1次方，然后乘上分子
- 取分子和分母的对数，减去，然后将日志的基数提高到相同的功率
我不是特别喜欢这样的问题，因为我们基本上是在寻找愚蠢的技巧，但我们现在是。
以下是不使用除法运算符进行分割的Java代码。
private static int binaryDivide(int dividend, int divisor) { int current = 1; int denom = divisor; // This step is required to find the biggest current number which can be // divided with the number safely. while (denom <= dividend) { current <<= 1; denom <<= 1; } // Since we may have increased the denomitor more than dividend // thus we need to go back one shift, and same would apply for current. denom >>= 1; current >>= 1; int answer = 0; // Now deal with the smaller number. while (current != 0) { if (dividend >= denom) { dividend -= denom; answer |= current; } current >>= 1; denom >>= 1; } return answer; }
主要概念：
假设我们计算20/4 ，那么
4*(1+1) = 8 *(1+1) = 16 *(1+1) == 32 (which is bigger) X so go back to 16 and try 16*(1+0.5) == 24 (bigger) X so go back to 16 and try 16*(1+0.25) == 20
代码：
float product=1,multiplier=2,a=1; int steps=0; void divCore(float number, float divideBy,float lastDivison) { steps++; //epsilon check eg (10/3) will never ends if(number - divideBy < 0.01) return; else { lastDivison = divideBy; divideBy *= multiplier; if(number >= divideBy) { product *= multiplier; divCore(number,divideBy,lastDivison); } else { a *= 0.5; multiplier = 1 + a; divCore(number,lastDivison,lastDivison); } } } float Divide(float numerator, float denominator) { //init data int neg=(numerator<0)?-1:1; neg*=(denominator<0)?-1:1; product = 1; multiplier = 2; a = 1; steps =0; divCore(abs(numerator),abs(denominator),0); return product*neg; }
（ 这是您不允许使用乘法的问题的解决scheme ）。
我喜欢这个解决scheme： https ://stackoverflow.com/a/5387432/1008519，但我觉得有点难以推理（尤其是|部分）。 这个解决scheme在我的脑海中更有意义：
var divide = function (dividend, divisor) { var result = 1; var denominator = divisor; // Double denominator value with bitwise shift until bigger than dividend while (dividend > denominator) { denominator <<= 1; result <<= 1; } // Minus divisor value until denominator is smaller than dividend while (denominator > dividend) { denominator -= divisor; result -= 1; } return result; }
- 我们将结果初始化为1（因为我们将把分母加倍，直到它大于分红）
- 加倍我们的分母（按位移），直到它大于股息
- 既然我们知道我们的分母大于我们的分红，我们可以减去我们的分母，直到它低于我们的分红
- 返回结果，因为分母现在尽可能接近使用除数的结果
以下是一些testing运行：
console.log(divide(16, 3)); // 5 console.log(divide(16, 33)); // 0 console.log(divide(972, 5)); // 194 console.log(divide(384, 15)); // 25
这是一个处理0除数情况和负的红利和/或除数的要点： https ： //gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130
由于OP说这是一个面试问题，所以我认为面试官除了要看你的编程技巧之外，还要看看下面的内容。 （假设你正在使用Java）
-
如何处理负数？ 将股息和除数转换为正数是很常见的。 但是，您可能会忘记
Math.abs(Integer.MIN_VALUE)仍然是Integer.MIN_VALUE。 因此，当股息为Integer.MIN_VALUE时，您应该分开计算。 -
“Integer.MIN_VALUE / -1”的结果是什么？ Integer中没有这样的值。 你应该和面试官讨论一下。 你可以为这种情况抛出exception。
这里是这个问题的Java代码，你可以validation它leetcode：分成两个整数 ：
public int divide(int dividend, int divisor) { if(divisor == 0) throw new Exception("Zero as divisor!"); int a = Math.abs(dividend); int b = Math.abs(divisor); boolean isPos = true; if(dividend < 0) isPos = !isPos; if(divisor < 0) isPos = !isPos; if(divisor == Integer.MIN_VALUE){ if(dividend == Integer.MIN_VALUE) return 1; else return 0; } if(dividend == Integer.MIN_VALUE) { if(divisor == -1){ // the result is out of Integer's range. throw new Exception("Invalid result."); } else { // Because Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE // we avoid it by adding a positive divisor to Integer.MIN_VALUE // here I combined two cases: divisor > 0 and divisor < 0 return divide((dividend + b), divisor) - divisor/b; } } int res = 0; int product = b; while(a >= b){ int multiplier = 1; while(a - product >= product){ product = product << 1;// "product << 1" is actually "product * 2" multiplier = multiplier << 1; } res += multiplier; a -= product; product = b; } return isPos?res:-res; }
这里是一个不使用'/'运算符的int整数分解方法：
public static int divide(int numerator, int denominator) throws Exception { int q = 0; boolean isNumPos = (numerator >= 0) ? true : false; boolean isDenPos = (denominator >= 0) ? true : false; if (denominator == 0) throw new Exception("Divide by 0: not an integer result"); numerator = Math.abs(numerator); denominator = Math.abs(denominator); while (denominator <= numerator) { numerator -= denominator; q++; } return (isNumPos ^ isDenPos) ? -q : q; }
简单的Python实现使用基本的高中math。 分母只是负数1的数字。
def divide(a, b): return a * b ** -1
以下是JavaScript中的一个：
function divideWithoutDivision(a, b, precision) { precision = precision > 0 ? precision : 10 var result = 0 var decimalPosition = 1 var A = a*0.1 var howManyTimes = 0 while (precision--) { A = A * 10 howManyTimes = 0 while (A >= b) { A = A - b howManyTimes += 1 } result = result + howManyTimes*decimalPosition decimalPosition = decimalPosition * 0.1 } return result } document.write('<br>20/3 = ', divideWithoutDivision(20, 3)) document.write('<br>10/3 = ', divideWithoutDivision(10, 3)) document.write('<br>10/4 = ', divideWithoutDivision(10, 4)) document.write('<br>17/14 = ', divideWithoutDivision(17, 14)) document.write('<br>23/4 = ', divideWithoutDivision(23, 4))
两个号码的分配不使用/
int div(int a,int b){ if(b == 0) return -1; //undefined else if (b == 1) return 1; else if(b > 1){ int count = 0; for(int i=b;i<=a;i+=b){ count++; } } return count; }
也许你可以devise一个方法来使用>>（位移）序列与其他按位运算符。 在维基百科中有一个伪代码示例：位运算符文章。
那么，如果这只是整数/整数= inttypes除法，通过加上n + n + n + n得到x / n = int.dec的整数部分是相当容易的，直到n大于x，然后减去1你的'n'数。
要获得int / int = real而不使用*，/，％或其他math函数，可以做几件事情。 例如，您可以将其余部分作为理性返回。 这具有确切的优点。 你也可以使用string修改把你的r变成r0 …（你select精度），然后重复相同的加法技巧，然后连接结果。
当然，你也可以试着找点乐子。
我不知道这是不是一个“愚蠢的把戏”，因为它是一个testing，你可以使用简单的东西（加法，减法）来build立一个复杂的事物（分裂）。 这是你的潜在雇主可能需要的技能，因为没有一个操作员的一切。 像这样的问题应该（理论上）排除那些不能从可以devisealgorithm的人那里去掉。
我认为这是一个问题，答案是在互联网上随时可用，但这是一个实施问题。
这是解决我的问题的function：
func printRemainderAndQuotient(numerator: Int,divisor: Int) { var multiplier = 0 var differene = numerator - divisor var dynamicNumber = 0 if divisor == 0 { print("invalid divisor") return } if divisor == numerator { print("quotient : " + "1") print("remainder : " + "0") return } while differene >= divisor { multiplier = multiplier + 1 dynamicNumber = divisor * multiplier differene = numerator - dynamicNumber } print("quotient : " + "\(multiplier)") print("remainder : " + "\(differene)") }
好吧，让我们看看… x / y = e ^（ln（x）-ln（y））
private int divideBy2(int number){ int count = 1; while(count<=number){ if(count*2==number){ return count; } count++; } return count; }
