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

このページの概要

以下は目次です。

• 目的
• 方法①（ビット演算を利用する）

目的

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

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

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

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

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

    引数
        x: 対象の値

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

方法①（ビット演算を利用する）

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

2 のべき乗の判定には、ビット演算（第４９章）が利用できます。

#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");
    }
}

実行結果：

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進法で表記すると、1000 や 100000 といったように、上位に 1 が 1つだけ立つかたちになっています。この性質を利用します。

やり方はいくつかありますが、ここでは、x と x - 1 のビット積（ビットAND）（第４９章）を取る方法を使っています。x が 1000 なら、x - 1 は 0111 になりますし、x が 100000 なら、x - 1 は 011111 になります。それぞれ、ビット積を取ると、0000 や 000000 が得られます。つまり、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 のときを特別扱いしていますが、次のように１つの文にまとめることも可能です。

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