Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

XOR для всех чисел от 1 до 2^N — 2 = 0 — доказывается элементарно (достаточно посмотреть на пары чисел 2^N — 2 и 1, 2^N — 3 и 2, 2^N — 4 и 3, и т.д.)
То есть, нужно найти ближайшую степень двойки и сделать XOR от 2 ^ X — 2 до N, где X целая часть от log2 N.

С Уважением, Andir!

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

не совсем понятно, как "4-битное беззнаковое целое" может быть "настолько велико..."
разве оно не лежит в пределе [0,15]?

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

4-битное или 4-байтное? Ну, да не суть важно.

Обозначим искомую функцию как F(N).

Утверждение 1.
F(4*K — 1) = 0 для любого целого K >= 1.

Доказательство.
По индукции.
1. Для K=1,2 можно проверить вручную.
2. Пусть верно для K. Перейдем к K+1.
F(4*(K+1) — 1) = 0 XOR 1 XOR 2 ... XOR (4*K-1) XOR (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3) = F(4*K — 1) XOR (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3) = 0 XOR (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3) = (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3)

Теперь посмотрим, что такое (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3).
4*K в двоичной записи имеет вид [что-то]00,
4*K+1 в двоичной записи имеет вид [что-то]01,
4*K+2 в двоичной записи имеет вид [что-то]10,
4*K+3 в двоичной записи имеет вид [что-то]11,

Это [что-то] — последовательность из 0 и 1, одинаковая для всех 4 чисел.
Отсюда видно, что (4*k) XOR (4*K+1) XOR (4*K+2) XOR (4*K+3) = 0.
Доказано.


А теперь уже легко понять, как посчитать F(N) для любого N. Для этого надо сделать не больше 3-х операций XOR.

Здравствуйте, Andir, Вы писали:

A>XOR для всех чисел от 1 до 2^N — 1 = 0 — доказывается элементарно (достаточно посмотреть на пары чисел 2^N — 2 и 1, 2^N — 3 и 2, 2^N — 4 и 3, и т.д.)

Маленькая ошибка закралась:
То есть, XOR всех чисел от 1 до 2^N — 2 даёт число со всеми единицами в разрядах == 2 ^ N — 1 и XOR на это число даёт 0.

С Уважением, Andir!

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

1,5,9,.... : XOR = 1
2,6,10,... : XOR = N+1
4,8,12,... : XOR = N

Здравствуйте, Eugene Sh, Вы писали:

ES>А теперь уже легко понять, как посчитать F(N) для любого N. Для этого надо сделать не больше 3-х операций XOR.
Даже можно так:

F(N) = N,   если N=4*k
F(N) = 1,   если N=4*k+1
F(N) = N+1, если N=4*k+2
F(N) = 0,   если N=4*k+3

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

1) Если число при делении на 4 дает в остатке 1 или 2, то в младшем разряде будет 1, иначе 0.
2) XOR чисел от 0 до 2^k-1 будет, очевидно, 0, т.к. перебираются все комбинации соответствующих 0 и 1 (на каждом месте ровно половину раз встретится 1).
3) Смотрим на старшую единицу, она на k-м месте, значит xor всех до нее даст ровно 2^k. Потом она будет участвовать в каждом следующем числе, т.е. если N нечетное, то в этом разряде будет 0, а если четное -- 1. Для младших разрядов после числа 2^k все начинается, как бы, с чистого листа, потому как 1 xor 2 xor ... xor 2^k = 2^k = 100000...0. Значит там применяем аналогичную логику.

В итоге:
— если число нечетное, то мы получим либо 0, либо 1, в зависимости от того, какой остаток при делении на 4, а именно, если в двух младших разрядах стоит x1, то результат будет x xor 1.
— если число четное, то оно, согласно тому, что выше, сохранится полностью, но в младшем разряде иногда может вместо нуля появиться 1, когда остаток от деления на 4 равен 2, т.е. когда в младших двух разрядах стоят 10.

unsigned __int64 xorall(unsigned __int64 n) {
    return n & 1 ? ((n >> 1) & 1) ^ 1 : n + ((n >> 1) & 1);
}

Здравствуйте, nikov, Вы писали:

N>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

Оно?

Здравствуйте, makes, Вы писали:

N>>Дано 4-битное беззнаковое целое число N. Надо найти XOR всех чисел от 0 до N включительно. Число N может быть настолько велико, что N итераций цикла делать слишком долго.

M>не совсем понятно, как "4-битное беззнаковое целое" может быть "настолько велико..."
M>разве оно не лежит в пределе [0,15]?

Шестерка не пропечаталась. Имелось в виду 64-битное.