Java Арифметический сумматор

Question

Я нашел код для добавления двух чисел с помощью XOR и AND без использования каких-либо арифметических операторов.

Я понимаю, что x^y приравнивается к сумме и что x & y приравнивается к переносу. Однако я не понимаю, почему перенос должен быть смещен? Мое знание левого побитового сдвига - это то же самое, что и умножение на два. Почему перенос размножается на два?

public static int add(int x, int y) { 

    // Iterate till there is no carry 
    while (y != 0) 
    { 
     // carry 
     int carry = x & y; 

     // Sum 
     x = x^y; 


     y = carry << 1; 
    } 
    return x; 

} 

Любое руководство оценили.

Answer 1

Давайте попробуем с двумя небольшими целыми х = 5, двоичный эквивалент 101 и у = 1, что двоичный эквивалент 001.

Теперь, почему я говорю о двоичном или более конкретно, хотят иметь дело с битами ? Поскольку XOR - это немного мудрая операция.

Итак, если вы запустите операцию XOR между х и у, результат следующий:

х = х^у = 101^001 = 100 (десятичное: 4)

See, просто операция XOR между двумя числами не дают нам суммы. (сумма 5 и 1 должна быть 6, а не 4). Мы используем перенос, чтобы получить точную сумму. На самом деле алгоритм разработан таким образом, чтобы он дал правильный ответ.

Теперь давайте посмотрим, как использовать перенос в этом алгоритме, дает нам правильный ответ.

Так,

перенос = х & у = 101 & 001 = 1 (десятичное 1)

Согласно программе, у = несут < < 1;

Так, у теперь станет = 001 < < 1 = 010 (десятичное: 2)

Цикл будет продолжать работать, пока у не станет равным нулю.

Если запустить цикл снова (так как у = 2, а не ноль)

х = х^у = 100^010 = 110 (десятичное: 6)

переноса = х & у = 100 & 010 = 0 (десятичное 0)

Теперь XOR между новым значением х и у 6, который в точности сумма 5 и 1. Посмотрите на ручной клади, его значение теперь 0.

Теперь наш y также станет 0, потому что правое смещение 0 также даст нам 0. Так как y теперь равно нулю, цикл больше не будет работать, и мы получили нашу сумму, вернув x!