Решение побитового уравнения

Question

У меня есть побитовое уравнение вида

X = (A & X) + (B & X)

, где A and B - известные целые числа, а X - неизвестно. Как мне найти ИКС? Здесь & - побитовое И, + - арифметическое c сложение, A, B и X - целые числа.

Одно из тривиальных решений равно нулю, но я должен вернуть его, если нет других решение возможно.

Мой подход: я знаю диапазон X, поэтому я мог бы перебрать его в O (n), чтобы проверить условие, но диапазон может быть очень большим, поэтому он может быть неэффективным.

Кроме того, я попытался выполнить AND операции с обеих сторон, чтобы сократить уравнение, но не смог найти значимого решения.

Answer 1

Давайте начнем с того, что сосредоточимся только на одном бите Х, самом последнем бите. Это может быть 0 или 1, и в зависимости от того, как А и В структурированы, мы можем исключить некоторые опции. Существует четыре комбинации последних битов A и B, но на самом деле нужно рассмотреть только три случая из-за симметрии:

• Случай 1: A и B заканчиваются нулем. В этом случае A & X заканчивается на 0, а B & X заканчивается на 0. Поэтому, поскольку X = A & X + B & X, последний бит X должен быть 0.
• Случай 2: один из A и B оканчивается на 1, а другой оканчивается на 0. Предположим, без ограничения общности, что A оканчивается на 1, а B оканчивается на 0. Тогда A & X + B & X = 0 + X = X, так что любой выбор бита для последнего бита X работает.
• Случай 3: A и B заканчиваются на 1. В этом случае A & X заканчивается на последний бит X и B & X заканчивается последним битом X. Тогда последний бит X дается как A & X + B & X = X + X = 2 X = 0, так как умножение любой бит на два и поиск самого младшего результирующего бита дает 0.

По-разному, в каждом случае для комбинации A и B битов мы можем определить, какой бит (ы) возможны для X путем обращения к таблице и перемещения одной позиции вправо для обработки следующего бита. Таблица, в частности, показана здесь

 A | B | X
---+---+---
 0 | 0 | 0
 0 | 1 | any
 1 | 0 | any
 1 | 1 | 0

Обратите внимание, что это соответствует вашей интуиции, что ноль - это всегда решение, так как эти правила позволяют вам выбрать 0 для любого бита, который вы хотите. Но если вы хотите найти решение, которое не везде равно 0, просто введите 1 в любое время, когда у вас есть выбор.

В качестве примера предположим, что A в двоичном виде - 011101001 и B в двоичном виде - 001101010. Затем, используя эту таблицу, у нас есть следующие опции:

    A 011101001
    B 001101010
    X 0*00000*0

Это дает четыре возможности:

010000010
010000000
000000010
000000000

И мы можем проверить, что, действительно, каждый из них является решением X = A & X + B & X.

Это решение выполняется за время O (b), где b - количество бит в числах A и B. Это O (log A + log B) , если вам даны числовые значения A и B, это означает, что это на путь быстрее, чем поиск методом перебора.

Надеюсь, это поможет!