先頭へ戻る

2のべき乗かどうかを判定する | Programming Place Plus C言語編 逆引き

Programming Place Plus トップページ -- C言語編 -- 逆引き

先頭へ戻る

この章の概要

この章の概要です。

目的

ある整数が 2 のべき乗かどうかを判定したいとします。

2、4、8 といった数は 2 のべき乗ですが、3、7、10 といった数は 2 のべき乗ではありません。

注意が必要なのは、0 と 1 と負数です。0 と負数は 2 のべき乗ではありません。1 は 2 のべき乗です(20 == 1)。


ここでは、次のように関数化することを考えます。

/*
    2 のべき乗かどうかを判定する

    引数
        x: 対象の値

    戻り値
        x が 2 のべき乗なら true。
        そうでなければ false。
*/
bool is_pow2(unsigned int x);

方法①(ビット演算を利用する)

標準ライブラリには目的に合った関数がないので、自力で実装しなければなりません。

2 のべき乗の判定には、ビット演算(第49章)が利用できます。

#include <stdbool.h>
#include <stdio.h>

/*
    2 のべき乗かどうかを判定する

    引数
        x: 対象の値

    戻り値
        x が 2 のべき乗なら true。
        そうでなければ false。
*/
bool is_pow2(unsigned int x)
{
    if (x == 0) {
        return false;
    }
    return (x & (x - 1)) == 0;
}


int main(void)
{
    for (unsigned int i = 0; i <= 16; ++i) {
        printf("%u: %s\n", i, is_pow2(i) ? "true" : "false");
    }

    return 0;
}

実行結果:

0: false
1: true
2: true
3: false
4: true
5: false
6: false
7: false
8: true
9: false
10: false
11: false
12: false
13: false
14: false
15: false
16: true

(x & (x - 1)) == 0 という式で判定しています。

x が 2 のべき乗であるとき、x を 2進法で表記すると、1000100000 といったように、上位に 1 が 1つだけ立つかたちになっています。この性質を利用します。

やり方はいくつかありますが、ここでは、x と x - 1 のビット積(ビットAND)(第49章)を取る方法を使っています。x が 1000 なら、x - 1 は 0111 になりますし、x が 100000 なら、x - 1 は 011111 になります。それぞれ、ビット積を取ると、0000000000 が得られます。つまり、0 になるわけです。

x が 2 のべき乗でないときには、0 になりません。たとえば、x が 1100 のような場合、x - 1 は 1011 なので、ビット積を取ると 1000 になり 0 にはなりません。

注意が必要なのは x が 0 のときです。説明のために 4ビットしかないと仮定すると、0 は 0000 になります。x - 1 は 1111 です(x は符号無し整数なので、0 を -1 すると最大値に戻ってきます)。よって、両者のビット積を取ると、0000 になります。これだと 0 は 2 のべき乗だということになってしまいます。そのため、0 の場合だけは例外的に扱わなければなりません。サンプルプログラムでは、先に if文を使って 0 のときを特別扱いしていますが、次のように1つの文にまとめることも可能です。

return (x != 0) && (x & (x - 1)) == 0;


参考リンク


更新履歴



逆引きのトップページへ

C言語編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー