Обратимость XOR

Программирование
#1

Здравствуйте. Вот есть такой код:

 int maxShuffle = buffer.Length - 3;

          
                for (int i = 0; i < buffer.Length; ++i)
                {
                    for (int idx = 1; idx <= maxShuffle; ++idx)
                    {
                        if (i - idx >= 0)
                        {
                            buffer[i] ^= buffer[i - idx];
                        }
                    }
                }

                for (int i = buffer.Length - 1; i >= 0; --i)
                {
                    for (int idx = 1; idx <= maxShuffle; ++idx)
                    {
                        if (i + idx < buffer.Length)
                        {
                            buffer[i] ^= buffer[i + idx];
                        }
                    }
                }

На вход подаются данные

31, 1, 18, 17, 18, 17, 3, 30, 26, 25, 15, 2, 20, 2, 24, 2, 28, 3, 27, 1

На выходе получаю такое:

2, 9, 16, 0, 0, 17, 15, 25, 7, 21, 27, 27, 0, 12, 0, 4, 1, 24, 3, 4

Меня интересут как обратить этот код?? Чтобы из нижнего варианта получался исходный. Это вообще возможно??

#2

Нужно просто повторить все операции xor в обратном порядке:

for (int i = 0; i < buffer.Length; ++i)
{
    for (int idx = 1; idx <= maxShuffle; ++idx)
    {
        if (i + idx < buffer.Length)
        {
            buffer[i] ^= buffer[i + idx];
        }
    }
}

for (int i = buffer.Length - 1; i >= 0; --i)
{
    for (int idx = 1; idx <= maxShuffle; ++idx)
    {
        if (i - idx >= 0)
        {
            buffer[i] ^= buffer[i - idx];
        }
    }
}

Поменял циклы местами, и исходный порядок обхода элементов по i поменял на обратный, но внутренние циклы по idx не стал менять на обратные, так как получается одно и то же.

#3

Огонь … все работает )) А у меня изначально была идея сделать карту индексов перестановок. Но этот код круче. Спасибо.

#5

Кстати, можно отказаться от цикла по idx (при текущем алгоритме). Тогда код из первого сообщения будет выглядеть так:

int maxShuffle = buffer.Length - 3;
int xorer = 0;

for (int i = 0; i < buffer.Length; ++i)
{
    buffer[i] ^= xorer;
    xorer ^= buffer[i];
    if (i - maxShuffle >= 0)
    {
        xorer ^= buffer[i - maxShuffle];
    }
}

xorer = 0;
for (int i = buffer.Length - 1; i >= 0; --i)
{
    buffer[i] ^= xorer;
    xorer ^= buffer[i];
    if (i + maxShuffle < buffer.Length)
    {
        xorer ^= buffer[i + maxShuffle];
    }
}
#6

Так может быть это какой то классический метод ?? просто после декомпилятора я смог восстановить только в таком виде …

#7

Не знаю, может и классический, ничего на ум не приходит. Может быть у авторов исходного кода была причина делать внутренний цикл. Просто именно в данном случае вместо перебора предыдущих maxShuffle элементов можно хранить их XOR в одной переменной, а потом “изымать” самый первый элемент и “добавлять” самый последний элемент из них.