有没有人能告诉我一种高效的方法，在不使用'/'的情况下进行除法操作。我可以使用类似于二分查找的方法，在log(n)步骤内计算出整数值。
115/3
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....
但是否有其他更有效率的方法？
不使用 '/' 实现除法
53
- broun
5
为什么不直接相减对数，然后再求指数？你可以解释一下为什么不使用除法，否则我们就无法知道问题出在哪里。 - user85109
6你是怎么得出57的？你可以除以2吗？ - Thilo
@thilo：就像我们在数组中进行二分搜索一样，我尝试找到商。 - broun
可能是重复的问题：如何使用位运算符实现除法。 - Stephen C
Knuth第2卷第4章 - Mike Wise
16个回答
132
通常的方法是进行移位和减法。这基本上与我们在学校里学到的长除法非常相似。最大的区别在于，在十进制除法中，您需要估算结果的下一位数字，而在二进制中，这很简单。下一个数字始终是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之间的任何数字，因此我们必须进行乘法运算以找到我们将从被除数中减去的中间结果。 在二进制中，这个数字只会是0或1。 我们永远不需要做乘法，因为我们只会乘以0或1（我们通常在if语句中处理 - 要么减去，要么不减去）。
-----------
101)1111001100
我们的第一步是找出结果中的第一个数字。我们要用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。
让我们考虑一下它与上面的代码的关系。我们首先将除数左移，直到它大于被除数。然后我们反复右移它，并且对于每次右移，检查该值是否小于我们在上次减法后得到的中间值。如果小于，我们再次进行减法，并在我们的结果中为该数字填充1。如果大于，我们“减去0”（不执行任何操作）并在结果中填充一个'0'（这不需要我们执行任何操作，因为这些数字已经被设置为0）。
当我们填好所有数字时，那就是我们的结果，而我们还没有减去的任何金额就是我们的余数。
有些人问我为什么在代码中使用|=而不是+=。我希望这可以解释为什么。虽然在这种情况下它们产生相同的结果，但我不认为将每个数字添加到现有的部分答案中。相反，我认为答案中的这个位置为空，而or只是填充它。
- Jerry Coffin
9
我花了一些时间才找到解决方案。有趣的是，为了理解它，我做了 Khan Academy 的长除法系列课程。它帮助填补了一些空白。 - Ahmed Nawar
这也有助于基本概念 http://www.homeschoolmath.net/teaching/md/long_division_why.php - Ahmed Nawar
在这个算法中（感谢如此详细的帖子），在执行以下部分时，使用左移是否会导致int溢出的问题：“while（denom <= dividend）{
denom <<= 1;
current <<= 1;
}考虑如果我们想要进行255/254的计算，并假设我们有一个1字节的单词。所以这是FF / FE。在第一步中，FE <= FF为真，因此我们对FE进行了左移，这将产生1FC，但由于1被截断，我们只得到了FC，它仍然<= FF，因此我们继续移位，导致当前和分母值错误。我错了吗？需要一些保护措施来防止溢出吗？ - leonman30
1@Edward：现在基本上是针对无符号的。通常您需要注意输入的符号，将正数除以，然后将正确的符号应用于结果。 - Jerry Coffin
1@MurilloHenrique：它是O（N），其中N是一个字中的位数。因此，如果您正在除以32位数字，则限于32个移位（在每个方向上）。如果您正在处理64位字，则在每个方向上为64位（依此类推）。如果您更喜欢按可被除数的数量级来思考，则为O（log N）。 - Jerry Coffin
显示剩余4条评论
16
选项：
- 根据你在小学学过的长除法算法，自己编写除法算法。
- 取分母的-1次幂，并乘到分子上。
- 取分子和分母的对数，相减，然后将对数的底数提高到同样的幂次方。
- Rob Lachlan
10
使用基本的高中数学实现简单的Python代码。分母只是一个数的负幂。
def divide(a, b):
return a * b ** -1
- msbodw001
1
这应该是最高的。 - Jonathon J Howey
6
以下是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;
}
- Hemant
1
1我在想，当整数为负值时，这个算法是否也能工作？ - AlienOnEarth
4
(这是一个解决方案，当你不允许使用乘法时）。
我喜欢这个解决方案：https://dev59.com/E2435IYBdhLWcg3wfQJ9#5387432，但我发现它有点难以理解（特别是
我喜欢这个解决方案：https://dev59.com/E2435IYBdhLWcg3wfQJ9#5387432，但我发现它有点难以理解（特别是
|部分）。这个解决方案在我的脑海中更加合理：var divide = function (dividend, divisor) {
// Handle 0 divisor
if (divisor === 0) {
return NaN;
}
// Handle negative numbers
var isNegative = false;
if (dividend < 0) {
// Change sign
dividend = ~dividend+1;
isNegative = !isNegative;
}
if (divisor < 0) {
// Change sign
divisor = ~divisor+1;
isNegative = !isNegative;
}
/**
* Main algorithm
*/
var result = 1;
var denominator = divisor;
// Double denominator value with bitwise shift until bigger than dividend
while (dividend > denominator) {
denominator <<= 1;
result <<= 1;
}
// Subtract divisor value until denominator is smaller than dividend
while (denominator > dividend) {
denominator -= divisor;
result -= 1;
}
// If one of dividend or divisor was negative, change sign of result
if (isNegative) {
result = ~result+1;
}
return result;
}
- 将结果初始化为1（因为我们会使分母加倍，直到它大于被除数）
- 通过位移将分母加倍，直到它大于被除数
- 由于我们知道分母比被除数大，所以可以用除数减去被除数，直到被除数小于除数
- 返回记录的操作，以尽可能接近分母使用除数的步骤
以下是一些测试运行：
console.log(divide(-16, 3)); // -5
console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(16, 0)); // NaN
console.log(divide(384, 15)); // 25
这里有个要处理0除数情况和负被除数或除数的代码片段：https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130
- mlunoe
3
不使用 / 运算符进行两个数的除法
int div(int a,int b){
if(b == 0)
return -1; //undefined
else if (b == 1)
return a;
else if(b > 1){
int count = 0;
for(int i=b;i<=a;i+=b){
count++;
}
}
return count;
}
- Parthiban Manoharan
1
这是O(n)而不是O(log(n))。对于大数来说，它需要很长时间。 - das Keks
3
主要概念：
假设我们要计算
假设我们要计算
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 e.g (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;
}
- Zaza
3
自从 OP 说这是一道面试题后，我认为面试官想要看到您的编程技能之外的一些东西。 （假设您使用 Java）
1. 如何处理负数？将被除数和除数都转换为正数是很常见的。但是，您可能会忘记
2. "Integer.MIN_VALUE/-1" 的结果是什么？ 在整数中没有这样的值。您应该与面试官讨论。对于这种情况，您可以抛出异常。
以下是此问题的 Java 代码，您可以在 leetcode 上验证它： leetcode:divide two integers
1. 如何处理负数？将被除数和除数都转换为正数是很常见的。但是，您可能会忘记
Math.abs（Integer.MIN_VALUE） 仍然是 Integer.MIN_VALUE 。因此，当被除数为 Integer.MIN_VALUE 时，您应该单独计算它。2. "Integer.MIN_VALUE/-1" 的结果是什么？ 在整数中没有这样的值。您应该与面试官讨论。对于这种情况，您可以抛出异常。
以下是此问题的 Java 代码，您可以在 leetcode 上验证它： leetcode:divide two integers
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;
}
- ChuanRocks
2
这里是一种无需使用 '/' 运算符的整数简单除法方法：
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;
}
- Mrinal Shukla
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))- trusktr
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接