与えられた範囲内でxを言う数がいくつあるか知りたいのですが、xのバイナリ表現の1の数が偶数である場合にlとr、l <rとしましょう。それを見つける効率的な方法はありますか？
重要な事実は次のとおりです。
あるプロパティPを持つ範囲[ l、r）の整数の数を数える必要があり、lが0である任意の範囲でこの問題を解決する方法を知っているとします。（ "[ l、r）"は "半分です。 -open範囲」：すべての整数N L ≤ N < R。これにより、算術演算が簡単になります。）次に、l ≠0の一般的な問題を解決するために減算する必要があります。COUNT[ l、r）= COUNT [0、r）− COUNT [0、l）。
最初の事実は、nに対してのみ機能するため、私たちが知る必要のあるすべてを完全に教えてくれるわけではありません。ただし、nが奇数の場合、n-1は偶数であり、必要なのはn-1自体のパリティをチェックすることだけです。これは[0、n -1）の範囲外の余分な数です。
これらすべてをまとめると、範囲[ l、r）がある場合、カウントは次のように計算されます。
その最後の計算には、範囲の大きさに関係なく、最大2つのパリティ計算と、2つの除算と減算が必要です。
これが数学のサイトだとしたら、最初は重要な事実で主張を証明せざるを得ないかもしれませんが、これはCSなので、証明の概要で満足します。最初に、iが偶数の場合、PARITY（i）とPARITY（i +1）が異なることに注意してください（バイナリ表現は最後のビットでのみ異なるため）。逆に、iが奇数の場合、PARITY（i）とPARITY（i -1）は異なります。ここで、[0、n）のすべての整数を取り、それらを奇数パリティの整数のセットと偶数パリティのセットに分割し、準同型を検討します。
F（I）⇒ I +1場合iは偶数です。
F（I）⇒ I -1もしiが奇数です。
f（i）のパリティがiのパリティと異なるため、[0、n）の2つのサブセットの1つ上のfのイメージはもう1つのサブセットです。したがって、2つのサブセットは同じサイズです。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加