このページの解説は C99 をベースとしています。
以下は目次です。
ある整数が 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) {
("%u: %s\n", i, is_pow2(i) ? "true" : "false");
printf}
}
実行結果:
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)(第49章)を取る方法を使っています。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 のときを特別扱いしていますが、次のように1つの文にまとめることも可能です。
return (x != 0) && (x & (x - 1)) == 0;
return 0;
を削除(C言語編全体でのコードの統一)
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
![]() |
管理者情報 | プライバシーポリシー |