Какова обратная функция x XOR (x / 2)? - PullRequest
Новая
       2

Какова обратная функция x XOR (x / 2)?

7 голосов
/ 08 марта 2012

Что такое обратная функция x XOR (x/2)?

Существует ли система правил для решения уравнений, аналогичная алгебре, но с логическими операторами?

Ответы [ 4 ]

7 голосов
/ 08 марта 2012

Предположим, у нас есть число x из N битов. Вы могли бы написать это как: 

b(N-1) b(N-2) b(N-3) ... b(0)

где b(i) - номер бита i в номере (где 0 - младший бит).

x / 2 - это то же самое, что x смещенный влево на 1 бит. Давайте предположим, что числа без знака. Итак: 

x / 2 = 0 b(N-1) b(N-2) ... b(1)

Теперь мы XOR x с x / 2: 

x ^ (x / 2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1)

Обратите внимание, что самый правый бит (самый старший бит) это b(N-1)^0, то есть b(N-1). Другими словами, вы можете получить бит b(N-1) из результата немедленно. Если у вас есть этот бит, вы можете вычислить b(N-2), потому что второй бит результата равен b(N-2)^b(N-1) и вы уже знаете b(N-1). И так далее, вы можете вычислить все биты b(N-1) до b(0) исходного числа x.

3 голосов
/ 08 марта 2012

Я могу дать вам алгоритм в битах:

Предполагается, что у вас есть массив из n битов: 

b = [b1 .. bn] // b1-bn are 0 or 1

Исходный массив: 

x0 = b0
x1 = b1 ^ x0
x2 = b2 ^ x1

или вообще 

x[i] = b[i] ^ x[i-1]
0 голосов
/ 14 января 2016

Я знаю, что это старая тема, но я наткнулся на тот же вопрос и обнаружил небольшую хитрость. Если у вас есть n бит, вместо того, чтобы требовать n бит операций (например, ответ Джеспера), вы можете сделать это с помощью log2 (n) число операций:

Предположим, что y в начале программы равен x XOR (x / 2), вы можете выполнить следующую C-программу: 

INPUT : y

int i, x;
x = y;
for (i = 1; i < n; i <<= 1)
    x ^= x >> i;

OUTPUT : x

и вот вам решение.

  • «>>» - операция сдвига вправо. Например, число 13, 1101 в двоичном формате, если смещено на 1 справа, станет 110 в двоичном, таким образом, 13 >> 1 = 6. x >> i эквивалентно x / 2 ^ i (деление на целые числа, конечно)
  • «<<» - операция сдвига левого бита (i << = 1 эквивалентно i * = 2) </li>

Почему это работает? Давайте возьмем в качестве примера n = 5 битов и начнем с y = b4 b3 b2 b1 b0 (в двоичном виде: в следующем x также записано в двоичном формате, но i записано в десятичном виде)

  • Инициализация:

x = b4 b3 b2 b1 b0

  • Первый шаг: я = 1

x >> 1 = b4 b3 b2 b1, поэтому мы имеем x = b4 b3 b2 b1 b0 XOR b3 b2 b1 b0 = b4 (b3 ^ b4) (b2 ^ b3) (b1 ^ b2) (b0 ^ b1)

  • Второй шаг: я = 2

x >> 2 = b4 (b3 ^ b4) (b2 ^ b3), поэтому мы имеем x = b4 (b3 ^ b4) (b2 ^ b3) (b1 ^ b2) (b0 ^ b1) XOR b4 (b3 ^ b4) (b2 ^ b3) = b4 (b3 ^ b4) (b2 ^ b3 ^ b4) ( b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3)

  • Третий шаг: я = 4

x >> 4 = b4, поэтому мы имеем x = b4 (b3 ^ b4) (b2 ^ b3 ^ b4) (b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3) XOR b4 = b4 (b3 ^ b4) (b2 ^ b3 ^ b4) ( b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3 ^ b4)

  • Тогда i = 8, что больше 5, мы выходим из цикла.

И у нас есть желаемый вывод.

Цикл имеет log2 (n) итераций, потому что i начинается с 1 и умножается на 2 на каждом шаге, поэтому, чтобы i достиг n, мы должны сделать это log2 (n) раз.

0 голосов
/ 08 марта 2012

Предположим, Y = X ^ (X / 2)

Если вы хотите найти X, сделайте это 

X = 0

do

  X ^= Y
  Y /= 2

while Y != 0

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

...