では、ある自然数の2進数表示における1の個数を求めるにはどうすれば良いかということになるが、(1) のの桁が1かどうかの判定は 「を2で割った余りを求める」 b % 2または、1とビット毎の AND をとる b & 1とすれば良い。(2) のの桁が1かどうかの判定は 「を…

結論から言えば、ビット演算子を用いて bitCount( n ^ r ^ (n-r) )となる。ここで bitCount は引数の2進数表示における1の個数である。「二項係数の偶奇」という記事で説明したことから直ちに2で割れる回数は が成り立つ場所の個数に一致することがわかる。 …