Упростить обратную функцию Z = X ^ (X <<Y)

У меня возникают трудности с упрощением следующей функции в несколько атомарных бинарных операций, такое ощущение, что это возможно, однако я не могу этого сделать, я уже несколько часов чешу голову:

public UInt32 reverse_xor_lshift(UInt32 y, Int32 shift)
{
    var x = y & (UInt32)((1 << shift) - 1);

    for (int i = 0; i < (32 - shift); i++) {
        var bit = ((x & (1 << i)) >> i) ^ ((y & (1 << (shift + i))) >> (shift + i));

        x |= (UInt32)(bit << (shift + i));
    }

    return x;
}

функция выполняет только то, что она вычисляет обратное к Z = X ^ (X << Y), другими словами reverse_xor_lshift(Z, Y) == X

4 голоса | спросил Lu4 20 J000000Monday15 2015, 19:43:50

1 ответ


0

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

Примените преобразование z ^= z << i, где i начинается с shift и удваивается при каждой итерации.

В псевдокоде:

while (i < 32)
    x ^= x << i
    i *= 2

Это работает, потому что на первом шаге вы записываете младшие биты (незатронутые) тем местом, в котором они были «вставлены», таким образом «удаляя их». Тогда часть, которая была изменена на оригинал, в два раза шире. Тогда новое число будет иметь вид x ^ (x << k) ^ (x << k) ^ (x << 2k) = x ^ (x << 2k), что опять то же самое, но с двойным смещением, поэтому тот же трюк снова будет работать, декодирование еще больше оригинальных битов.

ответил harold 20 J000000Monday15 2015, 19:56:39

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132