2026-11-16
next_x.c
#include <inttypes.h>
#include <stdio.h>
static uint32_t next_x(uint32_t z) {
uint32_t xs = ((z & 0x55555555u) + 1) & 0x55555555u;
return xs | (z & 0xAAAAAAAAu);
}
int main(void) {
uint32_t z = 2;
for (int i = 0; i < 4; i++) {
printf("%" PRIu32 "\n", z);
z = next_x(z);
}
}
点 (x, y) の値 z は、x の各ビットを偶数番目、y の各ビットを奇数番目に交互に並べた32ビットの整数です。next_x は、点 (x, y) の値を受け取り、x を1つ進めた点 (x + 1, y) の値を、x と y に分解せずに返すつもりの関数です。プログラムは点 (0, 1) の値 2 から始めて x を3回進めるので、(0, 1)、(1, 1)、(2, 1)、(3, 1) の値 2、3、6、7 を1行ずつ出力するはずですが、いまは 2、3、2、3 が出力されます。
Answer
Wrong
static uint32_t next_x(uint32_t z) {
uint32_t xs = ((z & 0x55555555u) + 1) & 0x55555555u;
return xs | (z & 0xAAAAAAAAu);
}
z & 0x55555555u は x のビットだけを元の位置に残し、y のビットがあった奇数番目を0にします。ここに1を足すと、x の0ビット目が0なら1になるだけで済みます。(0, 1) の値2から3へ進めたのはこの場合です。ところが (1, 1) の値3では x の0ビット目が1なので、1を足すと繰り上がりが1ビット目へ移ります。1ビット目は y の位置で、そこは0にしてあるので繰り上がりは止まり、次の & 0x55555555u で消えます。x は2になるはずが0に戻り、値は (0, 1) の2になります。
x の i ビット目からの繰り上がりは、x の i + 1 ビット目、つまり z の 2i + 2 ビット目へ届かなければなりません。2進の足し算では繰り上がりは隣のビットにしか移らないので、間に0の y のビットが挟まっていると、繰り上がりは次の x のビットまで届きません。
Right
static uint32_t next_x(uint32_t z) {
uint32_t xs = ((z | 0xAAAAAAAAu) + 1) & 0x55555555u;
return xs | (z & 0xAAAAAAAAu);
}
y の位置を0ではなく1で埋めてから1を足します。1のビットに繰り上がりが来ると、そのビットは0になってさらに上へ繰り上がるので、y の位置はちょうど次の x のビットへ繰り上がりを渡す中継になります。値3なら、z | 0xAAAAAAAAu の下位4ビットは 1011 です。1を足すと0ビット目から1ビット目を通って2ビット目まで繰り上がり、1100 になります。& 0x55555555u で x のビットだけを取り出すと 0100、x = 2 です。そこに元の y のビット z & 0xAAAAAAAAu を戻して6になります。
y のビットは足し算の前に1で埋め、あとで元の値を戻すので、繰り上がりの中継に使っても y は変わりません。x の各ビットだけを見れば、間の y のビットを飛ばしてふつうに1を足したのと同じ結果になります。x が最大の65535なら、最上位まで繰り上がった1は32ビットの外へあふれ、x は0に戻ります。uint32_t の足し算なので、このあふれは未定義動作ではありません。