Как взять xor чисел от 1..n для заданного n? (например, 1^2^3^^n)?

Это проблема интервью, с которой я столкнулся, я знаю, как получить решение грубой силы, многократно выполняя XOR чисел, но я понятия не имею, как сделать это более эффективно.

Я видел это решение на сайтеcarecup:

typedef unsigned long long UINT64;

UINT64 getXOROne2N(UINT64 n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0;
}

Но я не совсем понимаю логику здесь даже с объяснением парня, может кто-нибудь объяснить, как это сделать?


algorithm bit-manipulation xor bitwise-xor
person Kamal    schedule 14.11.2015    source источник
comment
что тебе в этом непонятно?   -  person vish4071    schedule 14.11.2015
comment
правильное объяснение дано здесь.   -  person Shubham    schedule 14.11.2015
comment
Сложная часть может показаться старшими битами, где n показывает любой другой результат, дающий подсказку.   -  person greybeard    schedule 14.11.2015

Ответы (2)


arrow_upward
3
arrow_downward

Существует математический шаблон, который возникает, когда вы смотрите на ответ для возрастающих значений n. Это похоже на вращение с четырьмя шагами. Это связано с тем, что мы колеблемся между преобразованием нечетных и четных чисел в различные комбинации предыдущих четных и нечетных результатов. Каждый последующий xor приносит нам четверть пути вращения. Я продемонстрирую и объясню.

Давайте рассмотрим это на каждом конкретном случае, начиная с самого начала, n=1:

00000001

Обратите внимание, что в решении это находится в пределах case 1, где возвращаемый результат равен 1. Также обратите внимание, что это значение n нечетное, поэтому оно обязательно заканчивается на 1.

Теперь, когда мы вычислим решение для n=2, это будет решение предыдущего ответа, подвергнутое xoring с новым значением n:

00000001
       ^
00000010
--------
00000011

Обратите внимание, что это соответствует case 2 решения, где возвращаемый результат равен n + 1. Также обратите внимание, что в этом случае n четное, обязательно оканчивающееся на 0, поэтому при xoring к предыдущему результату 1 (нечетному) мы только переключаем дополнительные биты, и поэтому результат в любом подобном случае всегда будет n+1

Для следующего значения, естественно, результатом getXOROne2N(3) является предыдущий результат, обработанный 3. Интересно, что это стирает нас до нуля:

00000011
       ^
00000011
--------
00000000

Это имеет смысл, когда мы думаем об этом; результат для getXOROne2N(2) был n+1 = 2+1 = 3, поэтому вполне естественно, когда мы выполняем операцию xor в этом следующем значении вдоль (n+1), которое отменит все биты со знаком до 0. Также обратите внимание, что это попадает в case 3 в представленном вами решении.

Теперь каждый раз, когда мы вычисляем следующее значение getXOROne2N после того, как у нас будет 0, оно будет просто следующим значением n, поэтому getXOROne2N(4) равно 4.

00000000
       ^
00000100
--------
00000100

Обратите внимание, что это точно попадает в case 0 в представленном вами решении.

Теперь, поскольку 4, связанный xor с предыдущим результатом 0, является четным, результат обязательно имеет конечный 0. Таким образом, следующее значение в строке для xor в сгибе, 5, должно иметь эту предыдущую битовую конфигурацию, но с последним битом, установленным в 1, что означает, что когда мы выполняем операцию xor с предыдущим результатом для вычисления getXOROne2N(5), мы отменяем все, кроме последнего бита, и возвращаемся к 1:

00000100
       ^
00000101
--------
00000001

И таким образом мы формируем нашу ротацию. Следующий после этого выполнит операцию xor с четным числом и, таким образом, даст n+1 (нечетное), а следующий после этого отменит обратно на 0 (удаление нечетного числа для получения этого четного результата), а затем мы получим следующий n (которое должно быть четным), и, таким образом, xor в последующем нечетном следующем значении up отменит все биты, кроме последнего, который остается включенным, снова давая 1.

Это порочный круг! Но довольно аккуратно, я думаю.

person Danny McCue    schedule 14.11.2015

arrow_upward
2
arrow_downward

Первое, что нужно отметить, это то, что любые 4 числа в строке, начиная с числа, делящегося на 4, приведут к 0, если XOR:

    ...00 - starting with any binary digits
    ...01
    ...10
    ...11
XOR -----
        0 : 4 times (...), twice 1 for both lower digits

Фактически это означает, что только последние числа после max, делящиеся на 4, перед n действительно формируют фактический результат (вы можете сгруппировать все числа до этого в квадроциклах, каждый из которых дает 0).

Итак, приходит

%4    n               calc           result
0   ...00  ->  ...00 =               n
1   ...01  ->  ...00 XOR ...01 =     1
2   ...10  ->  ...10 XOR 1 = ...11 = n + 1
3   ...11  ->  ...11 XOR ...11 =     0
person Vasily Liaskovsky    schedule 14.11.2015