Добрый вечер.
Требуется найти сумму для заданного n: s = 0 ^ (n — 0) + 1 ^ (n — 1) + ... + i ^ (n — i) + ... + (n — 1) ^ (n — (n — 1)) + n ^ (n — n),
где ^ — операция xor (1 <= n <= 2,000,000,000).
Примеры:
n = 1, s = 2
n = 2, s = 4
n = 3, s = 12
n = 4, s = 12
n = 5, s = 22
Здравствуйте, Аноним, Вы писали:
А>Добрый вечер.
А>Требуется найти сумму для заданного n: s = 0 ^ (n — 0) + 1 ^ (n — 1) + ... + i ^ (n — i) + ... + (n — 1) ^ (n — (n — 1)) + n ^ (n — n),
А>где ^ — операция xor (1 <= n <= 2,000,000,000).
А>Примеры:
А> n = 1, s = 2
А> n = 2, s = 4
А> n = 3, s = 12
А> n = 4, s = 12
А> n = 5, s = 22
Считаем сумму по каждому номеру бита отдельно, учитывая перенос. Тогда биты идут чередующимися блоками из нулей и единиц по 2^i штук, соответственно в блоках по 2^(i + 1) повторяется одинаковый паттерн, остается только учесть разницу в остатке. Получается что-то вроде такого:
typedef long long int64;
int64 xor_sum(int n) {
int64 result = 0;
int64 carry = 0;
for (int i = 0; i < 31; ++i) {
int64 b = 1LL << i;
int64 B = 1LL << (i + 1);
int64 r = (n + 1) % B;
int64 m = (n + 1) / B;
if (r <= b) {
carry += 2 * m * (b - r);
} else {
carry += 2 * (m + 1) * (r - b);
}
result |= ((carry & 1) << i);
carry >>= 1;
}
result |= carry << 31;
return result;
}