Ответ 1

Это довольно умное решение - оно использует тот факт, что в XOR-проектах есть образец результатов. Функция 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].

Ответ 2

Добавив к 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 как добавлении, вы бы отбросили его. XOR - это XOR, что добавить, чтобы вычесть!

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

Помните свойства логических операторов. Работайте с ними почти как добавление или умножение, если это помогает. Чувствуется необычным, что и (&), xor (^) и или (|) ассоциативны, но они являются!

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

Ответ 3

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

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

Я хотел бы знать/понимать математическое доказательство, лежащее в основе данного кода, как описано в ответе @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];
}

Ответ 4

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

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) сложности.

Спасибо

Ответ 5

Для поддержки XOR от 0 до N приведенный код необходимо изменить, как показано ниже:

int f(int a) {
    int []res = {a, 1, a+1, 0};
    return res[a % 4];
}

int getXor(int a, int b) {
    return f(b) ^ f(a);
}

Ответ 6

Скажите, пожалуйста, почему F (A-1)? Я не могу понять ваше объяснение.