1ЗадачаMedium
XOR через ReLU-блоки
Условие
Реализуйте побитовый XOR двух неотрицательных чисел через простые ReLU-блоки.
Для каждого бита a_i и b_i значение XOR можно записать как:
relu(a_i - b_i) + relu(b_i - a_i)где relu(x) = max(0, x).
Сигнатура
def xor_relu(a: int, b: int, bits: int = 16) -> int:Обработайте младшие bits битов и верните целое число.
Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Проверка решения
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Сначала один бит
Проверьте таблицу истинности для relu(a_i - b_i) + relu(b_i - a_i).
- Соберите число обратно
После вычисления i-го бита добавьте bit_xor * 2 ** i.
Идея решения
У XOR для двух битов результат равен 1, когда биты различаются, и 0, когда совпадают. Для бинарных значений выражение relu(a_i - b_i) + relu(b_i - a_i) ровно это и делает: один из членов становится 1 только при несовпадении битов.
Эталонный код
def xor_relu(a: int, b: int, bits: int = 16) -> int:
def relu(x: int) -> int:
return x if x > 0 else 0
result = 0
for i in range(bits):
bit_a = (a // (2 ** i)) % 2
bit_b = (b // (2 ** i)) % 2
bit_xor = relu(bit_a - bit_b) + relu(bit_b - bit_a)
result += bit_xor * (2 ** i)
return resultСложность
Время: O(bits). Память: O(1).
Для каждого бита выполняется константное число арифметических операций.