Прямая формула для суммирования XOR

Question

Я должен XOR числа от 1 до N, существует ли прямая формула для этого?

Например, если N = 6, то 1^2^3^4^5^6 = 7 Я хочу сделать это без использования цикла, поэтому мне нужна формула O (1) (если есть)

Answer 1

Ваша формула N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) ):

int main()
{
    int S = 0;
    for (int N = 0; N < 50; ++N) {
        S = (S^N);
        int check = N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) );
        std::cout << "N = " << N << ": "  << S << ", " << check << std::endl;
        if (check != S) throw;
    }

    return 0;
}

Вывод:

N = 0: 0, 0             N = 1: 1, 1             N = 2: 3, 3
N = 3: 0, 0             N = 4: 4, 4             N = 5: 1, 1
N = 6: 7, 7             N = 7: 0, 0             N = 8: 8, 8
N = 9: 1, 1             N = 10: 11, 11          N = 11: 0, 0
N = 12: 12, 12          N = 13: 1, 1            N = 14: 15, 15
N = 15: 0, 0            N = 16: 16, 16          N = 17: 1, 1
N = 18: 19, 19          N = 19: 0, 0            N = 20: 20, 20
N = 21: 1, 1            N = 22: 23, 23          N = 23: 0, 0
N = 24: 24, 24          N = 25: 1, 1            N = 26: 27, 27
N = 27: 0, 0            N = 28: 28, 28          N = 29: 1, 1
N = 30: 31, 31          N = 31: 0, 0            N = 32: 32, 32
N = 33: 1, 1            N = 34: 35, 35          N = 35: 0, 0
N = 36: 36, 36          N = 37: 1, 1            N = 38: 39, 39
N = 39: 0, 0            N = 40: 40, 40          N = 41: 1, 1
N = 42: 43, 43          N = 43: 0, 0            N = 44: 44, 44
N = 45: 1, 1            N = 46: 47, 47          N = 47: 0, 0
N = 48: 48, 48          N = 49: 1, 1            N = 50: 51, 51

Объяснение:

1. Младший бит - это XOR между младшим битом и следующим битом.

2. Для каждого бита, кроме младшего бита, выполняется следующее:

   • , если N нечетно, то этот бит равен0.
   • если N четное, тогда этот бит равен соответствующему биту N.

Таким образом, для случая нечетного N результат всегда равен 0или 1.

Answer 2

редактировать
GSerg Опубликовал формулу без циклов, но по какой-то причине удалил ее (сейчас не восстановлено). Формула совершенно верна (не считая небольшой ошибки). Вот C ++ -подобная версия.

if n % 2 == 1 {
    result = (n % 4 == 1) ? 1 : 0;
} else {
    result = (n % 4 == 0) ? n : n + 1;
}

Можно доказать это по индукции, проверив все напоминания о делении по 4. Хотя, не представляю, как можно придумать это, не генерируя вывод и не видя регулярности.

Пожалуйста, объясните ваш подход немного подробнее.
Поскольку каждый бит не зависит от операции xor, вы можете рассчитать их отдельно.
Также, если вы посмотрите на k-й бит числа 0..n, он сформирует шаблон. Например, числа от 0 до 7 в двоичном виде.

000
001
010
011
100
101
110
111

Вы видите, что для k-го бита (k начинается с 0) есть 2^k нулей, 2^k единиц, затем 2^k нулей снова и т. Д.
Таким образом, вы можете для каждого бита вычислить, сколько их, фактически не проходя все числа от 1 до n.

Например, для k = 2 есть повторяющиеся блоки с 2^2 == 4 нулями и единицами. Тогда,

int ones = (n / 8) * 4; // full blocks
if (n % 8 >= 4) { // consider incomplete blocks in the end
    ones += n % 8 - 3;
}

Answer 3

Для нечетного N результат будет 1 или 0 (циклический, 0 для N=3, 1 для N=5, 0 для N=7 и т. Д.)

Для четных N результат равен либо N, либо N+1 (циклический, N + 1 для N=2, N для N=4, N + 1 для N=6, N для N=8 и т.д.).

псевдокод:

if (N mod 2) = 0
  if (N mod 4) = 0 then r = N else r = N+1
else
  if (N mod 4) = 1 then r = 1 else r = 0

Answer 4

Позволяет сказать, что функция, которая XOR все значения от 1 до N будет XOR (N), тогда

XOR(1) = 000 1 = 0 1 ( The 0 is the dec of bin 000)
XOR(2) = 001 1 = 1 1
XOR(3) = 000 0 = 0 0
XOR(4) = 010 0 = 2 0
XOR(5) = 000 1 = 0 1 
XOR(6) = 011 1 = 3 1
XOR(7) = 000 0 = 0 0
XOR(8) = 100 0 = 4 0
XOR(9) = 000 1 = 0 1
XOR(10)= 101 1 = 5 1
XOR(11)= 000 0 = 0 0
XOR(12)= 110 0 = 6 0

Я надеюсь, что вы можете увидеть шаблон. Это должно быть похоже и на другие номера.

Answer 5

Попробуйте:

LSB переключается каждый раз, когда N нечетно, поэтому мы можем сказать, что

 rez & 1 == (N & 1) ^ ((N >> 1) & 1)

Та же самая картина может наблюдаться для остальных битов.Каждый раз, когда биты B и B+1 (начиная с LSB) в N будут отличаться, бит B в результате должен быть установлен.

Таким образом, конечный результат будет (включаяN): rez = N ^ (N >> 1)

РЕДАКТИРОВАТЬ: извините, это было неправильно.правильный ответ:

для нечетного N: rez = (N ^ (N >> 1)) & 1

для четного N: rez = (N & ~1) | ((N ^ (N >> 1)) & 1)

Answer 6

этот метод избегает использования условных выражений F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

F(N)= (N&(b0-1)) | (b0^b1)

Если вы посмотрите на XOR первых нескольких чисел, которые вы получите:

N     |  F(N)
------+------
0001  |  0001
0010  |  0011
0011  |  0000
0100  |  0100
0101  |  0001
0110  |  0111
0111  |  0000
1000  |  1000
1001  |  0001

Надеюсь, вы заметите шаблон:

если N mod 4 = 1, чем F(N)=1
, если N mod 4 = 3, чем F(N)=0
, если N mod 4 = 0, чем F(N)=N
, если N mod 4 = 2, чем F(N)=N, нос первым битом, равным 1, поэтому N|1

сложная часть получает это в одном утверждении без условий, плохо объясняющих логику, которую я использовал для этого.

возьмите первые 2 значащих бита N, назовите их:

b0 и b1, и они получаются с:

b0 = N&1
b1 = N&3>>1

Обратите внимание, что если b0 == 1, мы должны 0 все биты, но если это не все биты, кроме первого, то остаются неизменными.Мы можем сделать это следующим образом:

N & (b0-1): это работает из-за дополнения 2, -1 равно числу со всеми битами, установленными в 1 и 1-1=0, поэтому, когда b0=1 thisприводит к F(N)=0 .. так что это первая часть функции:

F(N)= (N&(b0-1))...

теперь это будет работать для N mod 4 == 3 и 0, для других 2 случаев давайте рассмотрим только b1, b0 и F(N)0:

b0|b1|F(N)0
--+--+-----
 1| 1|    0
 0| 0|    0
 1| 0|    1
 0| 1|    1

Хорошо, надеюсь, эта таблица истинности выглядит знакомой!это b0 XOR b1 (b1^b0).так что теперь, когда мы знаем, как получить последний бит, давайте поместим это в нашу функцию:

F(N)=(N&(b0-1))|b0^b1

и все, функция без использования условных выражений.также это полезно, если вы хотите вычислить XOR из положительных чисел от a до b.Вы можете сделать: F(a) XOR F(b).

Answer 7

Отличный ответ Алексея Малистова! Вариант его формулы: n & 1 ? (n & 2) >> 1 ^ 1 : n | (n & 2) >> 1 или эквивалентно n & 1 ? !(n & 2) : n | (n & 2) >> 1.

Answer 8

Работает нормально, без проблем для любого n;

int xorn(unsigned int n)
{

    if (n % 4 == 0)
      return n;
   else if(n % 4 == 1)
       return 1;
   else if(n % 4 == 2)
       return n+1;
  else
       return 0;
}

Answer 9

Как насчет этого?

!(n&1)*n+(n%4&n%4<3)

Answer 10

С минимальным изменением исходной логики:

int xor = 0;
for (int i = 1; i <= N; i++) {
    xor ^= i;
}

Мы можем иметь:

int xor = 0;
for (int i = N - (N % 4); i <= N; i++) {
    xor ^= i;
}

У него есть цикл, но для его выполнения потребуется постоянное время.Количество повторений цикла for будет варьироваться от 1 до 4.