【题解】-HackerRank-2's complement

题目

https://www.hackerrank.com/challenges/2s-complement/problem

题意

求 $a$ 到 $b$ 之间的所有数的二进制补码表示的 1 的个数之和。

题解

  • 首先将问题转化为求 0~x 之间二进制表示的 1 的个数之和。
  • 然后按位考虑,第 $i$ 位的周期为 $2^{i+1}$,然后就随便累加一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int M = 31;
LL go(LL x, bool neg = false) {
LL s = neg ? x : 0;
FOR (i, 0, M + 5) {
LL xx = x >> (i + 1);
s += xx * (1LL << i);
s += max(0LL, x - (xx << (i + 1)) - (1LL << i));
}
return s;
}

LL solve(LL x) {
if (x < 0) return go(1 + x + (1LL << M), 1);
else return go((1LL << M), 1) + go(x + 1);
}

int main() {
int T; cin >> T;
while (T--) {
LL l, r; cin >> l >> r;
cout << solve(r) - solve(l - 1) << endl;
}
}