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

Question

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

Я видел это решение на careercup:

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; 
} 

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

Answer 1

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

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

00000001 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Это фактически означает, что только последние цифры после макс делится на 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