Может ли кто-нибудь объяснить мне (подробно), как умножить два объекта __int64 и проверить, подойдет ли результат в __int64.
Примечание. Не используйте подпрограммы, зависящие от компилятора или процессора.
Умножение __int64
Ответы (1)
не предполагая, что a и b положительны:
__int64 a,b;
//...
__int64 tmp_result = abs(a) * abs(b) ;
if (
( a && b ) &&
(
( tmp_result < abs(a) || tmp_result < abs(b) ) ||
( tmp_result / abs(a) != abs(b)) ||
( a == TYPE_MIN && b != 1) ||
( b == TYPE_MIN && a != 1)
)
)
std::cout << "overflow";
__int64 result = a * b;
РЕДАКТИРОВАТЬ: добавление в код угловых случаев.
РЕДАКТИРОВАТЬ: На мой взгляд, достаточно ( a && a * b / a != b).
person
Mihran Hovsepyan
schedule
30.04.2011
@Mihran, что будет, когда ты тренируешься на TYPE_MIN?
- person There is nothing we can do; 30.04.2011
Это не работает, подумайте
a = b = 1+2^33, затем a*b = 1 + 2^34 + 2^66 = 1 + 1^34, он переполнился, но вы этого не обнаруживаете.
- person Yakov Galka; 30.04.2011
@ Ничего не поделаешь @ybungalobill обе ошибки исправлены.
- person Mihran Hovsepyan; 30.04.2011
также необходимо уловить регистр
a == 0 || b == 0 перед оператором if.
- person rwong; 30.04.2011
@Mihran спасибо за ваш ответ. Еще не проверено, но предполагая, что это правильно (и я очень надеюсь, что это так), как насчет способа LeBlanc SafeInt выполнять длинное умножение? Этот парень приложил столько усилий, чтобы сделать это, и вы сделали это, если на самом деле меньше пяти строк. Поздравляю! (но только в том случае, если это полностью работоспособно со всеми закрытыми угловыми корпусами)
- person There is nothing we can do; 30.04.2011
Спасибо @ Мы ничего не можем поделать! Я думаю, нетрудно доказать, что мое последнее условие
( a && a * b / a != b) то, что вы хотите.
- person Mihran Hovsepyan; 30.04.2011
@Mihran Я удалил свой последний комментарий, потому что то, что я там сказал, было неправдой.
- person There is nothing we can do; 30.04.2011
@Mihran, ты имеешь в виду (a && a * b / a! = B) вместо всего остального?
- person There is nothing we can do; 30.04.2011
@ Мы ничего не можем сделать. Если TYPE_MIN равен -1 = ›TYPE - однобитный тип =› в наборе значений этого типа нет 1, только 0 и -1. Так что программа даст правильный ответ.
- person Mihran Hovsepyan; 30.04.2011
@Mihran you mean just ( a && a * b / a != b) instead of everything else? Да.
- person Mihran Hovsepyan; 30.04.2011
@Mihran, почему не просто (a * b / a! = B)?
- person There is nothing we can do; 30.04.2011
@ Мы ничего не можем сделать. Потому что мы не можем делить на 0.
- person Mihran Hovsepyan; 30.04.2011
@Mihran да, но если бы я должен был раньше проверить, равен ли один из них нулю, и сразу же вернул бы ноль, если это так (поскольку это касается умножения, а умножение на ноль является законным), тогда мне не пришлось бы проверять второй раз, я прав ?
- person There is nothing we can do; 30.04.2011
@Mihran с вашим последним способом (a && a * b / a! = B) при умножении подписанного char == SCHAR_MIN на -1 дает неверный результат, но первая версия, похоже, работает.
- person There is nothing we can do; 30.04.2011
@Mihran, но тогда ваша первая версия неверна для lhs = std :: numeric_limits ‹__int64› :: max () + 1 и rhs = -1;
- person There is nothing we can do; 30.04.2011
@ Мы ничего не можем сделать. Я проверил это, и происходит странная вещь. Да, умножение SCHAR_MIN на -1 дает неверный результат, но если я присвоил ему какое-то значение и только после разделения на
a (т.е. signed char x = a * b; if(x / a != b)), он даст правильный результат.
- person Mihran Hovsepyan; 30.04.2011
@Mihran but then your first ver is incorrect for lhs = std::numeric_limits<__int64>::max() + 1 and rhs = -1; @ Мы ничего не можем сделать, в этом случае lhs становится равным MIN_VALUE из __int64, поэтому проблема такая же, как и выше, и будет решена таким образом.
- person Mihran Hovsepyan; 30.04.2011
@Mihran ну тогда у вас есть uac и int conv. Но дело в том, что это работает не так, как должно. То же самое, если у вас lhs = TYPE_MAX + 1 и rhs = -1. это не обязательно должно быть __int64, int достаточно, чтобы тормозить ваш код Я изменил последнее предложение с подписанного char на int
- person There is nothing we can do; 30.04.2011
@ Мы ничего не можем сделать. Я уже ответил на этот вопрос.
TYPE_MAX + 1 == TYPE_MIN. А для случая lhs = TYPE_MIN rhs = -1 работают оба кода.
- person Mihran Hovsepyan; 30.04.2011
@ мы ничего не можем сделать. Взгляните на вопрос stackoverflow.com/questions/5841000/whats-the-problem Вы должны сохранить
a * b в отдельной переменной.
- person Mihran Hovsepyan; 30.04.2011
@Mihran честно, я собираюсь протестировать этот код в течение следующих нескольких часов и, надеюсь, это поможет. Спасибо
- person There is nothing we can do; 30.04.2011
@Mihran, @There: Я доказал, что
(a && a * b / a != b) верен, по крайней мере, для двух дополнений. Я просто уменьшил проблему до 16-битной версии и перебрал все возможные комбинации ввода. Думаю, я мог бы доказать это и для других представлений чисел, подражая их поведению при переполнении. Как только я это сделаю, я дам этому ответу +1.
- person Oliver Charlesworth; 30.04.2011
@ Оли, это отличные новости. Но в свете этого, почему ЛеБлан пытался заново изобрести велосипед в своем классе SafeInt? Я имею в виду, что его код настолько длинный, что если решение Миграна правильное, а это значит, что оно работает с любым типом, я скажу, что оно намного лучше, чем у Леблана. Каково твое мнение?
- person There is nothing we can do; 30.04.2011
@There: я не уверен, о каком решении вы говорите (ссылка?), Но я могу представить. Ответ вполне может заключаться в том, что это быстрее, чем выполнять 64-битное деление.
- person Oliver Charlesworth; 30.04.2011
@Oli google: SafeInt, LeBlanc. Я не понимаю, как он может быть быстрее, это решение (Миграна) вообще не зависит от какого-либо конкретного типа и представляет собой две чертовы строчки. Посмотрите его решение, и вы увидите, сколько строк занимает его метод.
- person There is nothing we can do; 30.04.2011
@There: В этом заголовке очень много всего. Не могли бы вы указать мне на соответствующую функцию или что-то еще?
- person Oliver Charlesworth; 30.04.2011
@There: В любом случае, 64-битное разделение, вероятно, медленное. Вы можете попробовать профилирование, чтобы узнать, что быстрее?
- person Oliver Charlesworth; 30.04.2011
@Oli, мы говорим здесь об умножении, поэтому мой совет - используйте ctrl + f в VS и введите multiply. Поверьте, если бы я мог, я бы сделал это за вас. Во-первых, вы не можете сделать вывод для себя, когда я говорю о классе safeint: почему, черт возьми, ЛеБлан пытался изобрести колесо в своем классе SafeInt, и вы просите у меня ссылку, теперь вы можете не беспокоиться, просматривая этот файл, чтобы найти соответствующую информацию. Только сейчас мне потребовалось меньше 30, чтобы найти его. Оли знаешь что? Не трать мое время зря!
- person There is nothing we can do; 01.05.2011
@There: Почему всегда с реакцией коленного рефлекса? Поверьте, я сделал несколько беглых поисков, но быстро сдался, потому что это очень сложный код, основанный на шаблонах. Я предполагал, что вам будет интересно потратить какое-то время на это, поскольку это вы задали вопрос (а я трачу на это время от всего сердца ...). Мое предложение состоит в том, что вместо того, чтобы гадать, что быстрее, вы их профилируете.
- person Oliver Charlesworth; 01.05.2011
@Oli Я говорю вам, почему всегда с реакцией коленного рефлекса, если вы скажете мне, что вы сказали в своем последнем комментарии, я был бы более чем счастлив дать вам точный номер строки в файле, но вы этого не сделали. А как насчет того, почему ЛеБлан пытался изобрести велосипед в своем классе SafeInt, не имея возможности понять, о чем я говорю? А как насчет профилировщика? Знаете ли вы что-нибудь хорошее о C ++? Я спросил несколько месяцев назад на SO об этом и что я получил в ответ? И не говорите мне, что вы делаете это по доброте души - у вас есть на то причины (не обязательно материальные).
- person There is nothing we can do; 01.05.2011
@Oli continue, но, тем не менее, для этого есть причина (что бы это ни было, всегда есть причина).
- person There is nothing we can do; 01.05.2011
@ Там: я не знал, кто такой Леблан; Я предполагал, что вы имеете в виду решение, которое кто-то опубликовал в качестве ответа на один из связанных вопросов здесь, на SO. Пожалуйста, в будущем не всегда предполагайте, что люди будут знать точно, о чем вы говорите; не помешает просто предоставить ссылку.
- person Oliver Charlesworth; 01.05.2011
@There: вам не обязательно нужен полноценный профилировщик. Вы можете просто запустить, скажем, миллион итераций для случайных входных данных и рассчитать результат (убедитесь, что вы используете самые высокие настройки оптимизации компилятора).
- person Oliver Charlesworth; 01.05.2011
@Oli, честно говоря, я мог бы быть слишком резким, но иногда серьезно, поэтому я имею дело с такими гениями, что теряю терпение. stackoverflow.com/questions/2851526/how- do-i-use-a-profiler, прочтите это (бегло просмотреть) и решите для себя, будут ли какие-либо из этих ссылок полезны для меня. Я спрашиваю о профилировщике для кода C ++, и никто из этих гениев, кажется, не возражает против этого.
- person There is nothing we can do; 01.05.2011
__int64сама не является специфической для Microsoft Visual Studio? - person Peter G. schedule 30.04.2011