任意の数以上の最小の2のべき乗を求めるという記事を見つけたので自分でも書いてみました。
どのような場面で使うかなどは、元記事の方を参照していただいて、この記事では、ビット演算を用いて求める方法について書きます。
コード
以下にコードを示します。
static uint nearPow2(int n)
{
// nが0以下の時は0とする。
if (n <= 0) return 0;
// (n & (n - 1)) == 0 の時は、nが2の冪乗であるため、そのままnを返す。
if ((n & (n - 1)) == 0) return (uint)n;
// bitシフトを用いて、2の冪乗を求める。
uint ret = 1;
while (n > 0) { ret <<= 1; n >>= 1; }
return ret;
}
2016/6/11 8:30修正
少しだけ原理の説明
2の冪乗か判定
ある数$n$が2の冪乗か判定するには、(n & (n - 1))
この式が、0と等しいかを調べます。ただし、$n=0$の場合は、正しく求めることができないので、先に定義します。
$n$が0から7までの時の例を示します。
n(10進) | n | n-1 | n & (n - 1) | 2の冪乗かどうか | 2の何乗か |
---|---|---|---|---|---|
0 | 000 | 111 | 000 | ✕ | - |
1 | 001 | 000 | 000 | ◯ | 0 |
2 | 010 | 001 | 000 | ◯ | 1 |
3 | 011 | 010 | 010 | ✕ | - |
4 | 100 | 011 | 000 | ◯ | 2 |
5 | 101 | 100 | 100 | ✕ | - |
6 | 110 | 101 | 100 | ✕ | - |
7 | 111 | 110 | 100 | ✕ | - |
上記のように、2の冪乗かの判定ができます。
2の冪乗という数は、2進数で、$MSb$(Most Significant bit : 最上位ビット)の1つのみが立っている状態です。
そして、2の冪乗-1
という数は、2の冪乗で立っているビットより小さい位のビットが全て立っている状態です。
つまり、それらの$AND$(論理積)を取ると$0$になります。
例) $8_{(10)}=1000_{(2)}$の判定
$1000 \space and \space 0111 = 0000$
論理積が$0$になったので、2の冪乗となる。
ビットシフトを用いて2の累乗を求める
元記事の方では、$n$が与えられる数とすると、2を $log_2(n)$の小数を切り捨てた値 乗することによって目的の値を求めていました。
今回は、2の冪乗を求めるということなので、bit演算(ビットシフト)を用いて求めてみます。
まず、ビットシフトとは?
2進数のビット列を右や左に任意のビット数だけ移動させることです。
これを使うと何が嬉しいかというと、2進数で、左に1ビットシフトするということはその値を2倍する
ことに等しいです。
また、同様に右に1ビットシフトするということは、その値を1/2倍する
ことと等しいです。
つまり、$\times2^p$ や$\div2^p$という操作が$p$ビットのシフト演算で求まるということです!(pは任意の正の整数)
上記のことを踏まえて考えると、任意の数以上の最小の2の冪乗を求めるには、
1をMSbのビットの番号分左にシフトする
事によって求まることがわかります。
例) $3_{(10)}=11_{(2)}$
$11$の$MSb$のビット番号は$2$。
$1$を左に$2$ビットシフトすると、$100_{(2)}=4_{(10)}$となり、答えは$4$となる。
MSbの高速な求め方(加筆予定)
コメントにあったMSbを畳み込みで計算する方法を説明したいと思います。
実行結果
実行確認用のコードを以下に示します。
using System;
class Program
{
static void Main()
{
Console.WriteLine($"-1 : {nearPow2(-1)}");
Console.WriteLine($"0 : {nearPow2(0)}");
Console.WriteLine($"1 : {nearPow2(1)}");
Console.WriteLine($"2 : {nearPow2(2)}");
Console.WriteLine($"3 : {nearPow2(3)}");
Console.WriteLine($"4 : {nearPow2(4)}");
Console.WriteLine($"7 : {nearPow2(7)}");
Console.WriteLine($"8 : {nearPow2(8)}");
Console.WriteLine($"0x7fffffff : {nearPow2((int)0x7fffffff)}");
}
static uint nearPow2(int n)
{
// nが0以下の時は0とする。
if (n <= 0) return 0;
// (n & (n - 1)) == 0 の時は、nが2の冪乗であるため、そのままnを返す。
if ((n & (n - 1)) == 0) return (uint)n;
// bitシフトを用いて、2の冪乗を求める。
uint ret = 1;
while (n > 0) { ret <<= 1; n >>= 1; }
return ret;
}
}
実行結果は以下に示します。
-1 : 0
0 : 0
1 : 1
2 : 2
3 : 4
4 : 4
7 : 8
8 : 8
0x7fffffff : 2147483648
2016/6/11 8:30修正