Namaran

Code daily. Without assist.

2026-10-04

count_bits.c

#include <stdio.h>

static int count_bits(int x) {
    int n = 0;
    for (; x != 0; x &= x - 1)
        n++;
    return n;
}

int main(void) {
    printf("%d\n", count_bits(5));
    printf("%d\n", count_bits(-8));
}

count_bits は、int の値を2進数で見たときの1の数を返すつもりの関数です。引数も標準入力も使わず、int は32ビットです。いまは 2 と 29 が出ることもありますが、UndefinedBehaviorSanitizer を付けてビルドすると、2つ目の呼び出しの途中で signed integer overflow を報告して止まります。本来は、どうビルドしても 2 と 29 が出て正常に終わるはずです。

Answer

Wrong

static int count_bits(int x) {
    int n = 0;
    for (; x != 0; x &= x - 1)

-8 は2の補数で 0xFFFFFFF8 と表され、下の3ビットを除く29ビットが1です。x &= x - 1 は最下位の1を下から順に消すので、28個消した時点で最上位の符号ビットだけが残り、x は 0x80000000、つまり INT_MIN になります。x はまだ 0 ではないので n が 29 になり、続く更新で INT_MIN - 1 を計算します。この値は int では表せません。

符号付き整数の演算結果が型の範囲を超えるのは未定義動作です。C23 で負の数の表し方が2の補数に決まった後も、この規則は変わっていません1。多くの環境では計算が折り返して INT_MAX になり、INT_MIN & INT_MAX が 0 なので 29 が出ますが、規格はこの結果を約束しません。UndefinedBehaviorSanitizer はこの引き算を見つけて止めます。

Right

static int count_bits(unsigned x) {

引数を unsigned にすると、-8 は呼び出しの時点で unsigned に変換されます。変換は 2の32乗を足した値になると決まっているので、ビット列は同じ 0xFFFFFFF8 です。符号なし整数の演算は 2の32乗を法として折り返すことも規格で決まっており、最後の 0x80000000 - 1 は 0x7FFFFFFF になるだけで、未定義動作は起きません。ループはそのままで、29回目に x が 0 になって止まります。

  1. C17 までは、1の補数と「符号と絶対値」の表し方も認められていました。C23 はこれを2の補数だけに絞りましたが、範囲を超えた演算を未定義動作とする規則には手を入れていません。