Сложение двух чисел с помощью битовой манипуляции
Я работаю над следующей практической задачей из GeeksForGeeks :
Напишите функцию Add (), которая возвращает сумму двух целых чисел. Функция не должна использовать ни один из арифметических операторов (+, ++, –, -, .. прием).
Данное решение в C# имеет вид:
public static int Add(int x, int y)
{
// Iterate till there is no carry
while (y != 0)
{
// carry now contains common set bits of x and y
int carry = x & y;
// Sum of bits of x and y where at least one of the bits is not set
x = x ^ y;
// Carry is shifted by one so that adding it to x gives the required sum
y = carry << 1;
}
return x;
}
Глядя на это решение, я понимаю, как это происходит; я могу следовать вместе с отладчиком и предвидеть изменения значения, прежде чем они придут. Но после прогулки по нему несколько раз я все еще не понимаю, почему это происходит. Если бы это возникло в интервью, мне пришлось бы полагаться на память, чтобы решить его, а не на реальное понимание того, как работает алгоритм.
Может ли кто-нибудь помочь объяснить, почему мы используем определенные операторы в определенных точках и что эти итоги должны представлять? Я знаю, что в коде уже есть комментарии, но я явно что-то упускаю...
3 ответов:
На каждой итерации у вас есть следующие шаги:
carry <- x & y // mark every location where the addition has a carry x <- x ^ y // sum without carries y <- carry << 1 // shift the carry left one column
На следующей итерации
x
содержит всю сумму , за исключением для битов переноса, которые находятся в y. эти переносы правильно ударяются один столбец влево, как если бы вы делали сложение на бумаге. Продолжайте делать это до тех пор, пока не останется больше переносных битов, о которых нужно беспокоиться.Очень кратко, это делает добавление так же, как вы или Я сделали бы это на бумаге, за исключением того, что вместо того, чтобы работать справа налево, оно делает все биты параллельно.
Десятичная арифметика сложнее двоичной, но, возможно, она помогает сравнивать их.
Алгоритм, который обычно преподают для сложения, состоит в том, чтобы пройти через цифры одну за другой, не забывая "нести единицу", когда это необходимо. В приведенном выше алгоритме это не совсем то, что происходит - скорее, все цифры добавляются и позволяют обернуть, и все переносы собираются, чтобы быть примененными все сразу на следующем шаге. В десятичной системе счисления это выглядело бы так это:123456 777777 ------ + 890123 001111 << 1 011110 ------ + 801233 010000 << 1 100000 ------ + 901233 000000 done
В двоичной арифметике сложение без переноса-это просто XOR.
То, что вы здесь имеете, - это случай двоичной математики о представлении в памяти: https://www.wikihow.com/Add-Binary-Numbers
Обычно при программировании на C# вы не беспокоитесь о том, как это представлено в памяти. 55% времени это не стоит усилий, 40% это хуже, чем просто использовать встроенные функции. А в ремейке 5% Вы должны спросить себя, почему вы не программируете на родном C++, ассемблере или чем-то подобном низком уровне начнем с способностей.
Comments