[Java] ある整数よりも大きい最小の2のべき乗を計算

　Android開発をしてて必要になったのだが、Androidに限らず通用するアルゴリズムなのでJavaと書いてみた。

　相変わらずやや長い前置き。
　さて、タイトルだけ読んでも「なんのこっちゃ」「まるでプログラム初級教本の課題のようだ」と思うだろうけど、これが必要になる場面がある。OpenGLで任意のビットマップイメージからテクスチャを作成する際に必要になるのだ。私が扱ったことのある3DCGライブラリがOpenGL ESだけなので、それを前提に書くが、他の3DCGライブラリでもテクスチャ回りは似たようなものだろうと思う。

　OpenGL ESでは生成できるテクスチャのサイズと形状に関して制約がある。正方形、かつ、一辺の長さが2のべき乗（ピクセル？）というものらしい。逆にこの制約を守ってないテクスチャを「非正方形テクスチャ」と言うらしい。基本的に非正方形テクスチャはサポートされない。実際、非正方形の画像をテクスチャ化しても致命的なエラーは起きないのだが、ハードウェア依存性が出たり、崩れるテクスチャがあったり（全てではない）、どうも不安定になってしまうことが分かった。
　しかしテクスチャとして貼り付けたい画像は非正方形であることのほうが多い。これに対して通常は「テクスチャは正方形で作成し、テクスチャマッピングの際に貼り付けるテクスチャ座標を長方形で指定する」という手法をとるようだ。つまり適当な2のべき乗サイズの正方形画像を用意して、そのなかにすっぽり目的の画像を合成したものをテクスチャとして読み込んでしまえば良い、テクスチャに貼り付ける際は必要部分だけ切り取る、という話。が、手動でそんなすっぽり正方形な画像を合成するのは面倒くさいので、テクスチャ読み込み処理の中で自動で画像合成してしまうのが望ましい。

　…という流れで、タイトルの処理が必要になる。テクスチャ用イメージ作成のために、目的画像をラップ出来る正方形の一辺の長さを算出する必要がある、というわけだ。例えば、40px×92pxの画像をテクスチャ化するには128px×128px（128=2^7）の正方形が必要になる。
　さてまず必要になるのは整数が2のべき乗がチェックする関数。

    /**
     * xが2のべき乗かどうか調べる関数
     * @param x
     * @return 2のべき乗ならtrue。0はfalse。
     */
    public static boolean isPowerOfTwo(int x){
        return x > 0 && (x & (x - 1)) == 0;
    }

偶に見かけるアルゴリズムだとは思う。ループなんてせずにビットマスク演算して一発判定である。
　で、あとは画像の縦と横のうち長い方よりも長さ以上の2のべき乗を探してやればよい。

    /**
     * 整数列のうち最大の整数を返す。
     * @param args 整数列
     * @return
     */
    public static int max(int... args){
        int max = 0;
        for(int i=0; i<args.length;i++){
            max = Math.max(max, args[i]);
        }
        return max;
    }
    
    /**
     * 整数列のうち最大の整数よりも大きい、最小の2のべき乗値を返す関数
     * 引数のうちの最大の整数が0以下の場合は0を返す。
     * 万が一32bit整数で表現可能範囲外になった場合も0を返す。
     * @param args 整数列
     * @return
     */
    public static int padToPowerOfTwo(int... args){
        int max = max(args);
        if(max<=0){
            return 0;
        }
        int ret = 0;
        if(!isPowerOfTwo(max)){
            //単純な実装（パフォーマンスはそこそこを想定）
            // isPowerOfTwo関数によりshift=0,1は見る必要なし
            for(int shift=2; shift<31; shift++){ // 32bit符号付整数なので30回シフト=2^31が限界
                ret = 1 << shift;                // 1を左シフトして2のべき乗を生成
                if(ret > max){
                    return ret;
                }
            }
        } else {
            ret = max;
        }
        return ret;
    }

　max関数はついでに実装した。今回は縦と横の2値だけなのでいらないんだけどｗ
　2のべき乗値の作成はループごとにかけ算して作成していっても良いのだけど、Javaのコンパイラがビットシフトとして変換してくれるか謎だったので、敢えて生で左シフト演算して作成。なんかもっと高速に動くアルゴリズムがありそうだが、そんな繰り返し使う予定でもないので、まぁこんなもんだろうと思う。（本当はisPowerOfTwoのようにうまくビット演算数回して導出できないか（計算量O(1)になるようなアルゴリズムを）探してみたのだが、ちょっと思いつかなかった）

　実際に、Androidで画像をラップする処理はまた今度。

　なんというか、頭の体操的な感じのものだが、毎回自作してたら面倒くさい類のものでもあるのでやる気のあるうちに確立しておこうと思って記事にした。こういうアルゴリズムとか3DCGの話って情報系の人は授業で習ったりするのかな。そう思うと情報系の授業も受けとけばよかったかなと思いつつ、べつに独学で問題ないかとも思いつつ。絶賛勉強中です。