d619: 奇摩知識

2021-07-07 21:46:47 +0800 CST Tags: bitwise, math

出處：https://zerojudge.tw/ShowProblem?problemid=d619
提交：https://zerojudge.tw/Submissions?problemid=d619&account=allllllan123456

問題：給你一個正整數 $N\in[1, 100000000]$，問你由 1 開始數到 $N$ 的這些整數們總共有多少個 1-bit？

解法：先觀察每個位元的規律，如果我們每個數字都只觀測從 LSB 開始起算的第 $i$ 個 (由 0 起算) bit 的話，以 0 為起始點往上數，都會是連續的 $2^i$ 個 0、連續的 $2^i$ 個 1 依序交錯出現，於是可以視 $2^{i+1}$ 個數字為一組。那麼從 0 開始數到 $N$ 的這 $N+1$ 個整數裡面，前面的 $(N+1) - \big((N+1)\ \text{mod}\ 2^{i+1}\big)$ 個數字是已經分好組的狀態，而且其中的 0、1 各半，因此 $\dfrac{(N+1) - \big((N+1)\ \text{mod}\ 2^{i+1}\big)}2$ 就是有分好組的部分的 1 的數量；那對於剩下湊不滿一組的 $(N+1)\ \text{mod}\ 2^{i+1}$ 個數字，只要先扣除掉前方的 $2^i$ 個 0，則剩餘後半段的部分就是湊不滿一組的 1 的數量了。最後 $i$ 只要從 0 加總到 $\lfloor\log_2(N)\rfloor$ (即 $N$ 的 MSB)：

　　　　　　　　　　$\displaystyle\sum_{i=0}^{\lfloor\log_2(N)\rfloor}\frac{(N+1) - \big((N+1)\ \text{mod}\ 2^{i+1}\big)}2 + \max\Big(0,\big((N+1)\ \text{mod}\ 2^{i+1}\big) - 2^i\Big)$

就是答案了！

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int n;
 6    while (cin >> n) { n++; // n := N+1
 7        int sum = 0;
 8        for (int b=1, b2, b3; b<n; b=b2) {
 9            b2 = b << 1; b3 = b2 - 1; // b := 2^i; b2 := 2^{i+1}; b3 := 2^{i+1}-1
10            sum = (sum + ((n&~b3)>>1) + max(0, (n&b3)-b)) % 1000000000;
11        }
12        cout << sum << '\n';
13    }
14    return 0;
15}