1

この問題を解決するアルゴリズムを見つける必要があります
。範囲 [x,y] の数値のすべての正のビットの合計を見つけます。
警告: x と y は非常に大きくなる可能性があります (1 から 10^20 まで)。
手伝ってくれてありがとう。

4

1 に答える 1

3

パターンを特定するために具体的な例を見ることは有益かもしれません。たとえば、20 ～ 25 です。バイナリ表現は次のとおりです。

20: 10100
21: 10101
22: 10110
23: 10111
24: 11000
25: 11001

列ごとに見ると、右端の列が常に 0 と 1 を交互に繰り返すことが明らかです。このことから、範囲に N 個の数値があり、N が偶数である場合、右端の列には N/2 ビットが含まれていると結論付けることができます。ここで、右端の列を無視して、残りのビットでパターンを識別しようとします。

1010
1010
1011
1011
1100
1100

リスト内の各数値は、正確に 1 回繰り返されます。1010 = 1010 進数に変換すると、これらの数値は、1011 = 11、 であることがわかります1100 = 12。これらの 2 つの観察結果を使用して、次のように結論付けることができbitsInRange(20, 25) = (27 - 20 - 1) + 2*bitsInRange(10,12)ます。私たちが特定した両方のパターンは、偶数の開始番号と奇数の終了番号に当てはまるため、式は次のように一般化できます。

bitsInRange(X,Y) =
if X is even and Y is odd:
    (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

しかし、奇数の開始番号または偶数の終了番号がある場合はどうなるでしょうか。上記の式は、これらの種類の数値では特定された 2 つのパターンが正確に同じではないため、これらの数値では機能しません。偶数と奇数の可能な組み合わせごとに別々の式を書いてみることもできますが、その方法は危険でFencepost Errorsでいっぱいです。次の重要な特性を利用すると、作業が楽になります。

bitsInRange(X, Y) = bitsInRange(X, Y-1) + numBits(Y)
bitsInRange(X, Y) = bitsInRange(X+1, Y) + numBits(X)

... ここで、単一の数値numBitsのビット数を指定します。1

これで、偶数範囲と奇数範囲の可能なすべての組み合わせに対して再帰式を書くことができます。（ちなみに、ベースケースも必要です）

function bitsInRange(X,Y):
    if X == Y:
        return numBits(X)
    if X is odd:
        return bitsInRange(X+1, Y) + numBits(X)
    if Y is even:
        return bitsInRange(X, Y-1) + numBits(Y)
    return (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

最終ケースは問題空間を半分に分割し、他のすべてのケースは問題を最終ケースにすばやく変換するため、式全体は対数の複雑さを持ちます。これは、[1, 10^20] のような大きな範囲のビットを取得しようとしている場合に適しています。そのような膨大な数の場合でも、bitsInRange約 200 回しか実行されません。

于 2012-06-21T19:56:32.673 に答える