403
правки
Изменения
м
- → —
Для построения элемента <tex>3\to2</tex> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.
Основная идея реализации {{- --}} отдельная обработка переносов и остатков.
Тогда первое число ответа <tex>a</tex> может быть получена так:
<tex>a_i = x_i \oplus y_i \oplus z_i</tex> ,
где <tex>x</tex>, <tex>y</tex> и <tex>z</tex> {{- --}} входные числа, а <tex>x_i</tex>, <tex>y_i</tex> и <tex>z_i</tex> {{--- }} соответствующие их <tex>i</tex>-е биты.
Второе же число <tex>b</tex> можно получить так:
b_{i + 1} & = \langle x_i, y_i, z_i \rangle
\end{cases}</tex> ,
где <tex>\langle x, y, z\rangle</tex> {{- --}} функция медианы (она же "голосование 2 из 3"). С помощью этой функции считается перенос.
Очевидно, полученные числа <tex>a</tex> и <tex>b</tex> дадут в сумме <tex>x + y + z</tex>
