LoginSignup
12

More than 5 years have passed since last update.

任意の数以上の最小の2の冪乗を求める方法(bit 演算使用)

Last updated at Posted at 2016-06-10

任意の数以上の最小の2のべき乗を求めるという記事を見つけたので自分でも書いてみました。
どのような場面で使うかなどは、元記事の方を参照していただいて、この記事では、ビット演算を用いて求める方法について書きます。

コード

以下にコードを示します。

c#
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修正

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
12