そのような質問を見るとき、あなたはそれを簡単な断片に分解する必要があります。
たとえば、すべての番号に1がいくつあるかを知っているとすると[0, N]（これを呼びましょうones(N)）、次のようになります。
size_t ones(size_t N) { /* magic ! */ }
size_t count(size_t A, size_t B) {
return ones(B) - (A ? ones(A - 1) : 0);
}
このアプローチには、たとえば再帰を使用しoneてプログラムする方がおそらく簡単であるという利点があります。countそのため、最初の素朴な試みは次のようになります。
// Naive
size_t naive_ones(size_t N) {
if (N == 0) { return 0; }
return __builtin_popcount(N) + naive_ones(N-1);
}
しかし、これは遅すぎる可能性があります。単純にの値を計算する場合でも、2回count(B, A)計算することになります。naive_ones(A-1)
幸いなことに、ここで支援するメモ化は常にあり、変換は非常に簡単です。
size_t memo_ones(size_t N) {
static std::deque<size_t> Memo(1, 0);
for (size_t i = Memo.size(); i <= N; ++i) {
Memo.push_back(Memo[i-1] + __builtin_popcnt(i));
}
return Memo[N];
}
これは役立つ可能性がありますが、メモリの面でのコストは...不自由になる可能性があります。うーん。ones(1,000,000)コンピューティングのために、64ビットコンピューターで8MBのメモリを占有すると想像してみてください。よりまばらなメモ化が役立つ場合があります（たとえば、8番目または16番目のカウントごとにのみメモ化する）。
// count number of ones in (A, B]
static unoptimized_count(size_t A, size_t B) {
size_t result = 0;
for (size_t i = A + 1; i <= B; ++i) {
result += __builtin_popcount(i);
}
return result;
}
// something like this... be wary it's not tested.
size_t memo16_ones(size_t N) {
static std::vector<size_t> Memo(1, 0);
size_t const n16 = N - (N % 16);
for (size_t i = Memo.size(); i*16 <= n16; ++i) {
Memo.push_back(Memo[i-1] + unoptimized_count(16*(i-1), 16*i);
}
return Memo[n16/16] + unoptimized_count(n16, N);
}
ただし、メモリコストは削減されますが、主な速度の問題は解決されません。少なくとも__builtin_popcountB回使用する必要があります。そして、Bの値が大きい場合、これはキラーです。
上記の解決策は機械的であり、1オンスの思考を必要としませんでした。インタビューは、考えることよりもコードを書くことではないことがわかりました。
まですべての整数をばかげて列挙するよりも効率的にこの問題を解決できますBか？
最初のいくつかのエントリを検討するときに、私たちの頭脳（非常に素晴らしいパターンマシン）が何を拾うかを見てみましょう：
N bin 1s ones(N)
0 0000 0 0
1 0001 1 1
2 0010 1 2
3 0011 2 4
4 0100 1 5
5 0101 2 7
6 0110 2 9
7 0111 3 12
8 1000 1 13
9 1001 2 15
10 1010 2 17
11 1011 3 20
12 1100 2 22
13 1101 3 25
14 1110 3 28
15 1111 3 32
パターンに気づきましたか？私はそうします;）範囲8-15は0-7とまったく同じように構築されますが、行ごとにもう1つ=>転置のようです。そして、それも非常に論理的ですよね？
したがってones(15) - ones(7) = 8 + ones(7)、、、ones(7) - ones(3) = 4 + ones(3)およびones(1) - ones(0) = 1 + ones(0)。
さて、これを式にしましょう：
- リマインダー:(
ones(N) = popcount(N) + ones(N-1)ほぼ）定義上
- 私たちは今それを知っています
ones(2**n - 1) - ones(2**(n-1) - 1) = 2**(n-1) + ones(2**(n-1) - 1)
分離してみましょうones(2**n)。扱いが簡単です。次の点に注意してくださいpopcount(2**n) = 1。
- 再グループ化：
ones(2**n - 1) = 2**(n-1) + 2*ones(2**(n-1) - 1)
- 定義を使用します：
ones(2**n) - 1 = 2**(n-1) + 2*ones(2**(n-1)) - 2
- 単純化：
ones(2**n) = 2**(n-1) - 1 + 2*ones(2**(n-1))、でones(1) = 1。
クイック健全性チェック：
1 = 2**0 => 1 (bottom)
2 = 2**1 => 2 = 2**0 - 1 + 2 * ones(1)
4 = 2**2 => 5 = 2**1 - 1 + 2 * ones(2)
8 = 2**3 => 13 = 2**2 - 1 + 2 * ones(4)
16 = 2**4 => 33 = 2**3 - 1 + 2 * ones(8)
うまくいくようです！
しかし、私たちは完全には終わっていません。A必ずしも2の累乗であるとは限らない場合がありBます。それまで数えなければならない場合2**nでも、2**n + 2**(n-1)それはO（N）です。
一方、基数2で数値を表現できれば、新しく取得した数式を活用できるはずです。主な利点は、表現にlog2（N）ビットしかないことです。
例を選んで、それがどのように機能するかを理解しましょう。13 = 8 + 4 + 1
1 -> 0001
4 -> 0100
8 -> 1000
13 -> 1101
...ただし、カウントは単なる合計ではありません。
ones(13) != ones(8) + ones(4) + ones(1)
代わりに、「転置」戦略の観点から表現しましょう。
ones(13) - ones(8) = ones(5) + (13 - 8)
ones(5) - ones(4) = ones(1) + (5 - 4)
さて、少しの再帰で簡単にできます。
#include <cmath>
#include <iostream>
static double const Log2 = log(2);
// store ones(2**n) at P2Count[n]
static size_t P2Count[64] = {};
// Unfortunately, the conversion to double might lose some precision
// static size_t log2(size_t n) { return log(double(n - 1))/Log2 + 1; }
// __builtin_clz* returns the number of leading 0s
static size_t log2(size_t n) {
if (n == 0) { return 0; }
return sizeof(n) - __builtin_clzl(n) - 1;
}
static size_t ones(size_t n) {
if (n == 0) { return 0; }
if (n == 1) { return 1; }
size_t const lg2 = log2(n);
size_t const np2 = 1ul << lg2; // "next" power of 2
if (np2 == n) { return P2Count[lg2]; }
size_t const pp2 = np2 / 2; // "previous" power of 2
return ones(pp2) + ones(n - pp2) + (n - pp2);
} // ones
// reminder: ones(2**n) = 2**(n-1) - 1 + 2*ones(2**(n-1))
void initP2Count() {
P2Count[0] = 1;
for (size_t i = 1; i != 64; ++i) {
P2Count[i] = (1ul << (i-1)) - 1 + 2 * P2Count[i-1];
}
} // initP2Count
size_t count(size_t const A, size_t const B) {
if (A == 0) { return ones(B); }
return ones(B) - ones(A - 1);
} // count
そしてデモンストレーション：
int main() {
// Init table
initP2Count();
std::cout << "0: " << P2Count[0] << ", 1: " << P2Count[1] << ", 2: " << P2Count[2] << ", 3: " << P2Count[3] << "\n";
for (size_t i = 0; i != 16; ++i) {
std::cout << i << ": " << ones(i) << "\n";
}
std::cout << "count(7, 14): " << count(7, 14) << "\n";
}
勝利！
注：ダニエル・フィッシャーが指摘したように、これは負の数を説明できません（ただし、2の補数を仮定すると、正の数から推測できます）。