Найти XOR всех чисел в заданном диапазоне

вам дается большой диапазон [a, b], где 'a' и 'b' обычно могут быть от 1 до 4,000,000,000 включительно. Вы должны узнать XOR всех чисел в данном диапазоне.



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



может кто - нибудь помочь объяснить выигрышное решение:



long long f(long long a) {

     long long res[] = {a,1,a+1,0};

     return res[a%4];

}



long long getXor(long long a, long long b) {

     return f(b)^f(a-1);

}


здесь getXor() является фактической функцией для вычисления xor все числа в переданном диапазоне [a, b] и "f()" является вспомогательной функцией.

829   4  

4 ответов:

Это довольно умное решение-он использует тот факт, что есть шаблон результатов в запущенных XORs. Элемент f() функция вычисляет общий запуск XOR из [0, a]. Взгляните на эту таблицу для 4-разрядных чисел:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

где первый столбец-это двоичное представление, а затем десятичный результат и его отношение к его индексу (a) в списке XOR. Это происходит потому, что все верхние биты отменяются, а самые низкие два бита циклически повторяются каждые 4. Итак, вот как приходите к этой маленькой таблице поиска.

теперь рассмотрим для общего диапазона [a, b]. Мы можем использовать f() чтобы найти XOR для [0,a-1] и [0, b]. Так как любое значение XOR'D с собой равно нулю, то f(a-1) просто отменяет все значения в XOR выполнить меньше, чем a, оставляя вас с XOR диапазона [a, b].

124  
2014-01-23 12:51:55

добавление к большому ответу FatalError, линии return f(b)^f(a-1); можно было бы объяснить лучше. Короче говоря, это потому, что XOR имеет эти замечательные свойства:

  • это ассоциативные - поместите скобки, где вы хотите
  • это коммутативной - это означает, что вы можете перемещать операторов (они могут "коммутировать")

вот оба в действии:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c
  • это сторнирует сам

такой:

a ^ b = c
c ^ a = b

сложение и умножение-это два примера других ассоциативных / коммутативных операторов, но они не меняются местами. Итак, почему эти свойства важны? Ну, простой маршрут состоит в том, чтобы расширить его до того, что он есть на самом деле, а затем вы можете увидеть эти свойства на работе.

во-первых, давайте определим, что мы хотим и назовем это n:

n      = (a ^ a+1 ^ a+2 .. ^ b)

если это помогает, подумайте о XOR ( ^ ), как будто это это было дополнение.

давайте также определим функцию:

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

b больше a, поэтому, просто безопасно опустив несколько дополнительных скобок (которые мы можем, потому что это ассоциативно), мы также можем сказать следующее:

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

что упрощает до:

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

затем мы используем это свойство разворота и коммутативность, чтобы дать нам волшебную линию:

n      = f(b) ^ f(a-1)

если вы думали о XOR как о добавлении, вы я бы там зашел в вычитание. Гаммирования заключается в гаммирования, что добавить, убавить!

как мне самому это придумать?

запомните свойства логических операторов. Работать с ними почти как добавить или умножить, если это помогает. Он чувствует себя необычно, что и (&), исключающее ИЛИ (^) и или (|) являются ассоциативными, но они есть!

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

38  
2017-01-12 23:21:18

я узнал, что приведенный ниже код также работает как решение, приведенное в вопросе.

может быть, это немного оптимизировано, но это именно то, что я получил от наблюдения повторения, как указано в принятом ответе,

Я хотел бы знать / понимать математическое доказательство данного кода, как описано в ответе @Luke Briggs

вот этот JAVA-код

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}
2  
2017-02-07 11:08:44

Я решил проблему с помощью рекурсии. Я просто делю набор данных на почти равную часть для каждой итерации.

public int recursion(int M, int N) {
    if (N - M == 1) {
        return M ^ N;
    } else {
        int pivot = this.calculatePivot(M, N);
        if (pivot + 1 == N) {
            return this.recursion(M, pivot) ^ N;
        } else {
            return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
        }
    }
}
public int calculatePivot(int M, int N) {
    return (M + N) / 2;
}

позвольте мне знать ваши мысли над решением. Рад получить обратную связь по улучшению. Предложенное решение вычисляет XOR в 0 (log N) сложности.

спасибо

0  
2018-01-28 18:42:24

Comments

    Ничего не найдено.
Click here to cancel reply.