2026-11-11
flips.c
#include <stdbit.h>
#include <stdio.h>
int main(void) {
unsigned total = 0;
for (unsigned x = 0; x < 1024; x++) {
total += stdc_count_ones(x ^ (x + 1));
}
printf("%u\n", total);
}
これは何を出力するでしょうか?
Answer
Output
2047
x ^ (x + 1) は、x に1を足したときに値が変わったビットだけが1になる数です。1を足すと、最下位から続く1がすべて0になり、その1つ上の0が1になります。変わるのはこれらのビットだけなので、stdc_count_ones(x ^ (x + 1)) は「x から x + 1 へ進むときに反転したビットの数」を表します。
ループ全体の合計は、0 から1ずつ数えて 1024 に着くまでに、各ビットが反転した回数の合計です。これは桁ごとに数えられます。20 の位は1を足すたびに反転するので1024回、21 の位は2回に1回なので512回、一般に 2k の位は 1024 / 2k 回反転します。210 の位は、1023 から 1024 へ進む最後の1回だけです。合計は 1024 + 512 + … + 2 + 1 = 2047 になります。
1024個の x を1つずつ追うと、反転するビットの数は 1, 2, 1, 3, 1, 2, 1, 4, … と不揃いで、合計の見当がつきません。足す順番を「x ごと」から「桁ごと」に入れ替えると、各桁の回数は1024から半分ずつ減っていくので、等比数列の和1つで答えが出ます。