Может ли кто-нибудь сказать мне эффективный подход к выполнению операции деления без использования '/'. Я могу вычислить целочисленное значение в шагах 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, поэтому нам пришлось умножить, чтобы найти промежуточный результат, который мы собирались вычесть из дивиденда. В двоичном виде цифра всегда будет 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 соответственно.
Давайте рассмотрим, как это относится к приведенному выше коду. Начнем со смещения делителя влево, пока он не станет больше дивиденда. Затем мы несколько раз сдвигаем его вправо и для каждого сдвига вправо проверяем, меньше ли это значение, чем промежуточное значение, которое мы получили после последнего вычитания. Если оно меньше, мы снова вычитаем и заполняем 1 для этой цифры в нашем результате. Если оно больше, мы "вычитаем 0" (ничего не делаем) и заполняем "0" для этой цифры в результате (что, опять же, не требует от нас ничего делать, поскольку эти цифры уже установлены в 0).
Когда мы заполним все цифры, наш результат и любая оставшаяся сумма, которую мы еще не вычли, являются нашим остатком.
Некоторые спрашивают, почему я использовал |= вместо += в коде. Я надеюсь, что это помогает объяснить почему. Хотя в этом случае они дают одинаковый результат, я не думаю о добавлении каждой цифры к существующему частичному ответу. Скорее я думаю об этом месте в ответе как о пустом, и or просто заполняет его.
Параметры:
Мне не нравятся такие вопросы, потому что мы в основном ищем глупые трюки, но мы здесь.
Ниже приведен код 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;
}
Простая реализация Python с использованием базовой математики средней школы. Знаменатель - это просто число до степени отрицательного 1.
def divide(a, b):
return a * b ** -1
(Это решение проблемы, при которой вам также не разрешается использовать умножение).
Мне нравится это решение: fooobar.com/questions/142360/..., но мне сложно его рассуждать (особенно | -part). Это решение имеет немного больше смысла в моей голове:
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;
}
Вот несколько тестовых прогонов:
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
Поскольку ОП сказал, что это вопрос интервью, я думаю, что интервьюер хочет увидеть следующие вещи в дополнение к вашим навыкам кодирования. (Предположим, вы используете Java)
Как бороться с отрицательными цифрами? Обычно для преобразования как дивиденда, так и делителя в положительные числа. Однако вы можете забыть, что Math.abs(Integer.MIN_VALUE) по-прежнему Integer.MIN_VALUE. Поэтому, когда дивиденд Integer.MIN_VALUE, вы должны рассчитать его отдельно.
Каков результат "Integer.MIN_VALUE/-1"? В Integer такого значения нет. Вы должны обсудить это с интервьюером. Вы можете создать исключение для этого условия.
Вот код Java для этого вопроса, и вы можете проверить его 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 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;
}
Основная концепция:
Скажем, мы вычисляем 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;
}
Разделение двух чисел без использования /
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;
}
Вот простой метод разделения для 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;
}
Здесь один в 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))Возможно, вы можете разработать способ сделать это, используя последовательности → (сдвиги бит) с другими побитовыми операторами. Пример в psuedo-коде в статье Wikipedia: Побитовый оператор.
Ну, если это только деление типа integer/integer = int, довольно легко получить целую часть x/n = int.dec, добавив n + n + n + n, пока n не станет больше x, тогда вычитая один из вашего числа "n".
Чтобы получить int/int = real без использования *,/,% или других математических функций, вы могли бы сделать несколько вещей. Например, вы могли бы вернуть остаток как рациональный. Преимущество заключается в том, чтобы быть точным. Вы также можете использовать модификацию строки, чтобы превратить ваш r в r0... (вы выбираете точность), а затем повторите тот же трюк с добавлением, а затем объедините результаты.
И, конечно же, вы можете попробовать развлечься с переключением бит.
Я не знаю, так ли это "глупый трюк", поскольку это проверка того, насколько хорошо вы можете использовать простые вещи (сложение, вычитание) для создания сложной вещи (деления). Это навык, который может понадобиться вашему потенциальному работодателю, потому что для всего нет оператора. Подобный вопрос должен (теоретически) отсеять людей, которые не могут проектировать алгоритмы у людей, которые могут.
Я думаю, что проблема заключается в том, что ответ так легко доступен в Интернете, но проблема с реализацией.
Это функция, которая решила мою проблему:
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)")
}
Если вы берете деление как вычитание, в чем оно в основном, вы можете использовать метод "декремент", который позволяет вам не использовать какой-либо оператор вообще, кроме ~ в конце, чтобы инвертировать результат позже в положительное целое число или любое другое значение.
private static int decrement(int i) {
System.out.println("Value of decrement : ");
System.out.println(i);
return i - 1;
}
private static int divide(int n, int d) {
assert n > 0 && d > 0;
int counter = 0;
while (n >= d) {
for (int i = d; i > 0; i = decrement(i)) {
n = decrement(n);
}
counter = decrement(counter);
}
counter =~decrement(counter);
System.out.println(counter);
return counter;
}
хорошо, пусть см.... 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;
}