Блог

Я пытаюсь понять логику следующего кода, который суммирует 2 целых числа с помощью битовой манипуляции:

 def sum(a, b):
    while b != 0:
        carry = a amp; b
        a = a ^ b
        b = carry << 1

    return a
 

В качестве примера я использовал: a = 11 и b = 7

11 в двоичном представлении равно 1011 7 в двоичном представлении равно 0111

Затем я прошелся по алгоритму:

 iter #1: a = 1011, b = 0111
  carry = 0011 (3 decimal)
  a = 1100 (12 decimal)
  b = 0110 (6 decimal)

iter #2: a = 1100, b = 0110
  carry = 0100 (4 decimal)
  a = 1010 (10 decimal)
  b = 1000 (8 decimal)

iter #3: a = 1010, b = 1000
  carry = 1000 (8 decimal)
  a = 00010 (2 decimal)
  b = 10000 (16 decimal)

iter #4: a = 00010, b = 10000
  carry = 00000 (0 decimal)
  a = 10010 (18 decimal)
  b = 00000 (0 decimal)

We Done (because b is now 0).
 

Как мы видим, на всех итерациях a b всегда 18, что является правильным ответом.
Однако я не смог понять, что на самом деле здесь происходит. Значение a уменьшается и уменьшается с каждой итерацией, пока внезапно не достигнет 18 на последней итерации. Кроме того, можем ли мы что-нибудь узнать о ценности переноса во время процесса?

Я хотел бы понять интуицию, стоящую за этим.

Благодаря ответу @WJS, я думаю, что понял его.

 let's add 11 and 7 as before, but let's do it in the following order:
First, calculate it without the carry.
Second, calculate only the carry.
Then add both parts.

01011
00111
-----
01100 (neglecting carry)
00110 (finding only the carry)
-----
10010 (sum)
 

Теперь, чтобы найти первую часть, как мы можем избавиться от битов переноса? с КСОРОМ.
Чтобы найти вторую часть, мы используем И, а затем сдвигаем ее на 1 бит влево, чтобы поместить ее «под» правым битом.
Теперь все, что нам нужно сделать, это суммировать обе части. Весь смысл в том, чтобы не использовать оператор , так как же мы можем это сделать? Рекурсия!

Мы назначаем первую часть a и вторую часть b и повторяем этот процесс до тех пор, пока b=0 это не означает, что мы закончили.

Возможно, если вы возьмете более простой пример, это поможет.

 a = 11
b = 11
a amp; b == 11 since AND returns 1's where both bits in the same
position are 1. These are the carry bits.

Now get rid of the the carry locations using exclusive or
a = a ^ b == 00

But a `carry` would cause addition to add bits one position to
the left so shift the carry bits left by 1 bit.

b = carry << 1 = 110
now repeat the process

carry = a amp; b = 0 amp; 110 == 0 no more carries
b = carry << 1 == 0
done.
11   11 = 110 = 3   3 = 6

 

Понимание ролей (И) amp; и (XOR) ^ являются ключевыми. Применение их к несколько более сложным примерам должно помочь. Но игнорируйте промежуточные десятичные значения, так как они мало помогают. Думайте только о том, что происходит в двоичном коде.

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

Первым шагом является вычисление переноса, которое происходит только в двоичном формате, когда оба бита равны 1, поэтому aamp;b вычисляет это для каждого бита. Затем побитовое сложение происходит через XOR (игнорируя перенос), и XOR работает, потому что:

 0 0=0 (==0^0)
1 0=1 (==1^0)
1 1=0 (==1^1, generates carry bit which we ignore)
 

Следующий шаг-сдвинуть перенос влево (<