Namaran

Code daily. Without assist.

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 を右へずらして位置を数えてもかまいません。