2026-10-04
nth_bit.c
int nth_bit(unsigned x, int k) {
}
x を2進数で見て、1のビットを下から 0 番目、1 番目、2 番目と数えます。k 番目の1があるビットの位置(最下位のビットを 0 とする)を返す nth_bit を書いてください。k は 0 以上です。x の1が k 個以下しかないとき(x が 0 のときを含む)は -1 を返します。
入力例 1
nth_bit(0b101100, 0)
出力例 1
2
入力例 2
nth_bit(0b101100, 2)
出力例 2
5
入力例 3
nth_bit(0b101100, 3)
出力例 3
-1
Reference
#include <stdbit.h>
int nth_bit(unsigned x, int k) {
while (k-- > 0 && x != 0)
x &= x - 1;
return x == 0 ? -1 : (int)stdc_trailing_zeros(x);
}
参考実装は、下から k 個の1を消してから、残った最下位の1の位置を調べます。x &= x - 1 は最下位の1ビットだけを0にするので、これを k 回繰り返すと k 番目の1が最下位に来ます。入力例2の 0b101100 なら、2回消すと 0b100000 が残り、その位置は 5 です。
1が k 個以下しかなければ、途中で x が 0 になります。そこで消すのをやめ、最後に x == 0 を見て -1 を返します。この判定は省けません。stdc_trailing_zeros は最下位の1より下にある0の数を返す C23 の関数で、引数が 0 のときは型のビット幅(unsigned が32ビットなら 32)を返すからです。判定がなければ、入力例3は -1 ではなく 32 になります。
掲載したのは参考実装で、唯一の正解ではありません。<stdbit.h> を使わずに、x & 1 を見ながら x を右へずらして位置を数えてもかまいません。