xor
От: Аноним  
Дата: 30.04.08 14:18
Оценка:
Добрый вечер.

Требуется найти сумму для заданного 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
Re: xor
От: twisted_mind  
Дата: 02.05.08 20:46
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Добрый вечер.


А>Требуется найти сумму для заданного 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;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.