Другой способ умножить два числа без использования оператора "*"

Ответ 1

Я не знаю, должен ли это быть "программирующим вопросом". Но в Maths:

x * y = x / (1 / y) #divide by inverse

Так:

Способ 1:

public static double multiplier(double a, double b) {

    // return a / (1 / b);

    // the above may be too rough
    // Java doesn't know that "(a / (b / 0)) == 0"
    // a special case for zero should probably be added:

    return 0 == b ? 0 : a / (1 / b);
}

Метод 2 (более "программирование /API"):

Используйте большое десятичное целое число:

new BigDecimal("3").multiply(new BigDecimal("9"))

Есть, вероятно, еще несколько способов.

Ответ 2

Существует метод под названием " Русское крестьянское умножение". Продемонстрируйте это с помощью оператора сдвига,

public static int multiply(int n, int m)
{ 
    int ans = 0, count = 0;
    while (m > 0)
    {
        if (m % 2 == 1)             
            ans += n << count;
        count++;
        m /= 2;
    }

    return ans;
}

Идея состоит в том, чтобы удвоить первое число и вдвое увеличить второй номер, пока второе число не станет равным 1. В процессе, когда второе число становится нечетным, мы добавляем первое число в результат (результат инициализируется как 0). Другая реализация является,

static int russianPeasant(int n, int m) {
    int ans = 0;

    while (m > 0) {
        if ((m & 1) != 0)
            ans = ans + n;

        n = n << 1;
        m = m >> 1;
    }
    return ans;
}

см.

• https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/
• https://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/

Ответ 3

Другие затронули вопрос 1 достаточно, что я не собираюсь переделывать его здесь, но я действительно хотел немного затронуть вопрос 2, потому что мне кажется (мне) более интересным.

Итак, когда кто-то задает вам этот вопрос, они меньше озабочены тем, как выглядит ваш код, и больше озабочены тем, как вы думаете. В реальном мире вам никогда не придется писать умножение без оператора *; каждый язык программирования, известный человеку (за исключением Brainfuck, я думаю), имеет умножение, почти всегда с оператором *. Дело в том, что иногда вы работаете с кодом и по какой-либо причине (возможно, из-за раздувания библиотеки из-за ошибок конфигурации из-за несовместимости пакета и т.д.) Вы не сможете использовать библиотеку, к которой вы привыкли. Идея состоит в том, чтобы увидеть, как вы работаете в этих ситуациях.

Вопрос заключается не в том, что вы "вырезаны", чтобы быть программистом; навыки, подобные этим, могут быть изучены. Трюк, который я использую лично, - это думать о том, что именно представляет собой ожидаемый результат для вопроса, который они задают? В этом конкретном примере, как я (и я предполагаю, что вы тоже), изученный в 4 классе в начальной школе, умножение повторного добавления. Поэтому я бы это сделал (и имел в прошлом, у меня был такой же вопрос в нескольких интервью), когда цикл for делал повторное добавление.

Дело в том, что если вы не понимаете, что умножение - это повторное добавление (или любой другой вопрос, на который вас просят ответить), тогда вы просто будете ввернуты. Вот почему я не являюсь большим поклонником этих типов вопросов, потому что многие из них сводятся к мелочам, которые вы либо знаете, либо не знаете, вместо того, чтобы тестировать свои истинные навыки в качестве программиста (упомянутые выше навыки в отношении библиотеки и т.д. могут быть проверены гораздо лучше другими способами).

Ответ 4

TL; DR - сообщите интервьюеру, что повторное изобретательство колеса - плохая идея

Вместо того, чтобы развлекать вопрос интервьюера Code Golf, я бы ответил на другой вопрос:

Блестящие инженеры Intel, AMD, ARM и других производителей микропроцессоров десятилетиями мучились тем, как умножать 32-битные целые числа в наименьшем числе возможных циклов и на самом деле даже способны создать правильный, полный 64-битный результат умножения 32 битных целых чисел без переполнения.

(например, без предварительного литья a или b в long, умножение на 2 ints, например 123456728 * 23456789 переполняется на отрицательное число)

В этом отношении языки высокого уровня имеют только одно задание с такими целыми умножениями, как это, а именно, чтобы получить работу, выполняемую процессором, с минимальным количеством пуха.

Любая сумма Code Golf для тиражирования такого умножения в программном обеспечении IMO является безумием.

Там, несомненно, много hacks которые могли бы имитировать умножение, хотя многие из них будут работать только в ограниченных диапазонах значений a и b (фактически, ни один из трех методов, перечисленных в OP, не работает без ошибок для всех значений a и b, даже если мы игнорировать проблему переполнения). И все будет (на порядок) медленнее, чем инструкция IMUL.

Например, если либо a либо b является положительной мощностью 2, тогда может быть выполнено смещение бита другой переменной влево на журнал.

if (b == 2)
   return a << 1;
if (b == 4)
   return a << 2;
... 

Но это было бы очень утомительно.

В маловероятном случае, когда оператор * действительно исчезает в течение ночи из спецификации языка Java, в лучшем случае я бы использовал существующие библиотеки, которые содержат функции умножения, например BigInteger.multiply(), по тем же причинам - многолетнее критическое мышление умы ярче, чем мои, в производстве и тестировании таких библиотек.

BigInteger.multiply, очевидно, будет надежным до 64 бит и более, хотя возврат результата обратно в 32-битный int снова вызовет проблемы с переполнением.

Проблема с игровым оператором * Code Golf

Там присущи проблемы со всеми тремя решениями, указанными в вопросе ОП:

• Метод A (цикл) не будет работать, если первое число a отрицательно.

 for (int i = 0; i < a; i++) {
      resultat += b;
  }

Вернет 0 для любого отрицательного значения a, так как условие продолжения цикла никогда не выполняется

• В методе B у вас не будет стека для больших значений b в методе 2, если вы не реорганизуете код, чтобы разрешить оптимизацию хвостового вызова

multiplier(100, 1000000)

"main" java.lang.StackOverflowError

• И в методе 3 вы получите ошибки округления с log10 (не говоря уже о очевидных проблемах с попыткой взять журнал любого числа <= 0). например

multiplier(2389, 123123);

возвращает 294140846, но фактический ответ 294140847 (последние цифры 9 x 3 означают, что продукт должен заканчиваться на 7)

Даже ответ с использованием двух последовательных операторов деления двойной точности склонен к проблемам округления при повторном повторении двойного результата до целого числа:

static double multiply(double a, double b) {
    return 0 == (int)b 
       ? 0.0 
       : a / (1 / b);
}

например, для значения (int)multiply(1, 93) возвращает 92, потому что multiply возвращает 92.99999.... который усечен с возвратом в 32-битное целое число.

И, конечно, нам не нужно упоминать, что многие из этих алгоритмов O(N) или хуже, поэтому производительность будет ужасной.

Ответ 5

Для полноты:

Math.multiplyExact(int, int):

Возвращает произведение аргументов, вызывая исключение, если результат переполняет int.

если выбрасывание при переполнении допустимо.

Ответ 6

Если у вас нет целочисленных значений, вы можете воспользоваться другими математическими свойствами, чтобы получить произведение из двух чисел. Кто-то уже упоминал log10, так что здесь немного более неясное:

public double multiply(double x, double y) {
    Vector3d vx = new Vector3d(x, 0, 0);
    Vector3d vy = new Vector3d(0, y, 0);
    Vector3d result = new Vector3d().cross(vx, vy);
    return result.length();
}

Ответ 7

Одним из решений является использование битовых операций. Это немного похоже на ранее представленный ответ, но также исключает разделение. У нас может быть что-то вроде этого. Я буду использовать C, потому что я не очень хорошо знаю Java.

uint16_t multiply( uint16_t a, uint16_t b ) {
  uint16_t i = 0;
  uint16_t result = 0;

  for (i = 0; i < 16; i++) {
    if ( a & (1<<i) ) {
      result += b << i;
    }
  }
  return result;
}

Ответ 8

Вопросы, задаваемые интервьюерами, отражают их ценности. Многие программисты приносят свои навыки головоломки и математические соображения, и они считают, что эти навыки составляют лучших программистов.

Они ошибаются. Лучшие программисты работают над самым важным, а не самым интересным битом; сделать простой, скучный технический выбор; пиши понятно; думать о пользователях; и избегать глупых обходов. Хотелось бы, чтобы у меня были эти навыки и тенденции!

Если вы можете сделать несколько из этих вещей, а также выработать рабочий код, вам потребуются многие команды разработчиков. Вы можете быть суперзвездой.

Но что вы должны делать в интервью, когда вы в тупике?

Задавайте уточняющие вопросы. ("Какие числа?" "Какой язык программирования это не имеет умножения?" И, не будучи грубым: "Зачем я это делаю?") Если, как вы подозреваете, вопрос просто немой головоломки, не влияющие на реальность, эти вопросы не дадут полезных ответов. Но здравый смысл и желание попасть на "проблему, стоящую за проблемой", являются важными инженерными достоинствами.

Лучшее, что вы можете сделать в плохом интервью, - это продемонстрировать свои сильные стороны. Признание их зависит от вашего интервьюера; если они этого не сделают, что их потеря. Не обескураживайте. Есть и другие компании.

Ответ 9

Используйте BigInteger.multiply или BigDecimal.multiply если необходимо.