最初と最後のビットだけが1になっている数を出力するCプログラム

この記事では、与えられた数 n 以下の整数の中から、2進表現において最初と最後のビットだけが1(セットビット)になっている数をすべて出力する方法を解説します。

コンピュータの用語では、値が「1」のビットをセットビット、値が「0」のビットをアンセットビットと呼びます。

入力と出力の例

入力:num = 5
出力:1 3 5
    1 は 2進数で「1」
    3 は 2進数で「11」
    5 は 2進数で「101」

出力される数は「1」「11」「101」のように、先頭と末尾のビット以外がすべて0になっているのが特徴です。

アルゴリズム

START
ステップ1:unsigned int 型の変数 num=5 と int 型の変数 i=1 を宣言する
ステップ2:i の値(1)を出力する
ステップ3:i=3 から i<=num まで i を1ずつ増やしながら繰り返す
    もし (!(i-1 & i-2)) ならば
        i を出力する
    終了
終了
STOP

C言語による実装例

#include <stdio.h>
int main(int argc, char const *argv[]) {
    unsigned int num = 5;
    int i = 1;
    printf("%d ", i); /* 最初の数 1 を出力 */
    for (i = 3; i <= num; ++i) {
        if (!(i-1 & i-2)) /* i-1 と i-2 のAND演算 */
            printf("%d ", i);
    }
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

1 3 5

条件式「!(i-1 & i-2)」の仕組み

このプログラムのポイントは条件式です。i が「2のべき乗 + 1」の形(例:5=101、9=1001、17=10001)のとき、i-1 は最上位のビットだけが立ち、i-2 はそれより下位のビットがすべて立ちます。両者に共通して立っているビットが存在しないため、AND演算の結果は0となり、条件が真になります。

一方、途中のビットも立っている数(例:7=111)では、i-1=110 と i-2=101 のAND演算結果が0にならないため、出力から除外されます。

なお、この手法の時間計算量は O(n)、追加で必要なメモリは O(1) であり、シンプルながら効率的な判定方法です。