У меня есть числа XOR от 1 до N, существует ли для него прямая формула?
Например, если N = 6 then 1^2^3^4^5^6 = 7 Я хочу сделать это без использования какого-либо цикла, поэтому мне нужна формула O (1) (если она есть)
Прямая формула для суммирования XOR
Ответ 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
Объяснение:
-
Низкий бит - это XOR между младшим и следующим бит.
-
Для каждого бита, кроме младшего бита, выполняется следующее:
- если N нечетно, тогда бит равен 0.
- если N равно четному, этот бит равен соответствующему биту N.
Таким образом, для случая нечетного N результат всегда равен 0 или 1.
Ответ 2
изменить
GSerg Выложил формулу без циклов, но по какой-то причине удалила ее (теперь она восстановлена). Формула совершенно верна (кроме небольшой ошибки). Здесь С++-подобная версия.
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 zeroes, 2^k ones, затем 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;
}
Ответ 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
Ответ 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
Надеюсь, вы увидите рисунок. Он также должен быть аналогичным для других чисел.
Ответ 5
Попробуйте следующее:
LSB переключается каждый раз, когда N является нечетным, поэтому мы можем сказать, что
rez & 1 == (N & 1) ^ ((N >> 1) & 1)
Такую же картину можно наблюдать и для остальных бит.
Каждый раз, когда бит B и B+1 (начиная с LSB) в N будет отличаться, бит B в результате должен быть установлен.
Итак, конечный результат будет (включая N): rez = N ^ (N >> 1)
EDIT: извините, это было неправильно. правильный ответ:
для нечетного N: rez = (N ^ (N >> 1)) & 1
для четного N: rez = (N & ~1) | ((N ^ (N >> 1)) & 1)
Ответ 6
Отличный ответ Алексея Малистова! Вариант его формулы: n & 1 ? (n & 2) >> 1 ^ 1 : n | (n & 2) >> 1 или эквивалентно n & 1 ? !(n & 2) : n | (n & 2) >> 1.
Ответ 7
этот метод позволяет избежать использования условных выражений 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 это приводит к 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).
Ответ 8
С минимальным изменением исходной логики:
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.
Ответ 9
Как насчет этого?
!(n&1)*n+(n%4&n%4<3)
Ответ 10
Это прекрасно работает без каких-либо проблем для любого 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;
}
Ответ 11
Взгляните на это. Это решит вашу проблему.
fooobar.com/questions/76333/...
Чтобы вычислить сумму XOR от 1 до N:
int ans,mod=N%4;
if(mod==0) ans=N;
else if(mod==1) ans=1;
else if(mod==2) ans=N+1;
else if(mod==3) ans=0;
Ответ 12
Если кому-то это нужно, просто попробуйте решение python:
def XorSum(L):
res = 0
if (L-1)%4 == 0:
res = L-1
elif (L-1)%4 == 1:
res = 1
elif (L-1)%4 == 2:
res = (L-1)^1
else: #3
res= 0
return res
Ответ 13
почему Л-1? пожалуйста, объясните мне в деталях.