Ｃ言語で2の累乗（2^n）への切り上げ＆切り捨て

今回は 2の累乗の値への切り上げ＆切り捨てについて、効率的なＣ言語のコードの書き方をご紹介します。組込みファームウェアでは、2の累乗への丸めをする必要がままあります。例えばメモリのページサイズは2の累乗（例えば 0x1000 Byteとか）なので、必要なページ数を計算したりするのに使用します。

まずは手始めに、一般的な10の累乗での切り上げ＆切り捨ての方法を紹介します。そのあと、2の累乗での切り上げ＆切り捨ての方法をご紹介します。

10の累乗での切り上げ＆切り捨て

まずは手始めに、普通の10進数での切り上げ＆切り捨てを確認します。言い換えると、10の累乗（10, 100, 1000, 10000….）にて切り上げる処理です。

例えば 1234 という値を 100 で切り上げたとき＆切り捨てたときはどうなるでしょう？切り捨てた場合は 1200, 切り上げた場合は1300ですね。見ただけですぐできますね。

一般化するために式で書いてみる

パッと見て暗算できるんですが、ここはせっかくなので式にして一般化して見ましょう。Ｃ言語で書くと下記のようになります。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int val = 1234u;      /* 元の値 */
    unsigned int ceil_val;        /* 切り上げた値   */
    unsigned int floor_val;       /* 切り捨てした値 */
    unsigned int nth_power = 100u; /* 10の累乗 */

    /* 切り捨て */
    floor_val =  val                    - (val                     % nth_power); 
    
    /* 切り上げ */
    ceil_val  = (val + (nth_power - 1)) - ((val + (nth_power - 1)) % nth_power); 
    
    printf("val       : %d.\n", val);
    printf("floor_val : %d.\n", floor_val);
    printf("ceil_val  : %d.\n", ceil_val);
    
    return 0;
}

切り捨てコードの処理の解説

切り捨てについては、簡単ですね。1234 という値を 100 で切り捨てるときは、元の値 1234 から 34 を引けばいいです。34の求め方は、1234 を 100で割ったときの余りです。余りの計算（剰余算）は「％演算子」でできます。
ということで切り捨ては、1234 を val、100 を nth_power という変数名にすると、
val - (val % nth_power);
という式で計算できます。

切り上げコードの処理の解説

次は切り上げについて見ていきます。1234 という値を 100 で切り上げるときの考え方としては「100の位を1増やしてから切り捨てをする」とすればOKです。言い換えると、1234 に 100 を足して切り捨てをすると、元の値を切り上げした値 1300 となります。1234 を val、100 を nth_power という変数名としてＣ言語で書くと、
(val + nth_power) - ((val + nth_power) % nth_power);
となります。
これでも問題なさそうですが、実は1点まずいところがあります。もし元の値valが10の累乗だった場合に問題が起きます。例えばvalが1200だった場合、これを切り上げた値は1200のままです、すでにキリのいい値になっていますから、なにもする必要はありません。ですが下記の式で計算した場合、結果は1300になってしまいます。

もともと、100 で切り上げるときの考え方としては「100の位を1増やしてから切り捨てをする」というものでした。ですが、正確には「元の値が100の累乗出ない場合のみ、100の位を1増やしてから切り捨てをする」とする必要があります。
上記式では、100の位を1増やすために nth_power（100）を足していますが、元の値の時は100の位を変更しないようにするため、nth_power（100）から1を引いてものを足すようにします。
(val + (nth_power - 1)) - ((val + (nth_power - 1)) % nth_power);

これで正しく切り上げすることができるようになります。

2の累乗への切り上げ＆切り捨て

さて、本題の2の累乗への切り上げ＆切り捨てを考えます。2の累乗（0x2, 0x4, 0x8, 0x10, 0x20,….）にて切り上げる処理です。

例えば 0x1234 という値を 0x0100 で切り上げたとき＆切り捨てたときはどうなるでしょう？切り捨てた場合は 0x1200, 切り上げた場合は0x1300ですね。これも見ただけですぐできますね。

一般化するために式で書いてみる

2の累乗でも、実は10の累乗と同じ式で切り捨て＆切り上げができます。Ｃ言語で書くと下記のようになります。値とprintfのフォーマットを変えただけです。処理は全く変えていません。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int val = 0x1234u;       /* 元の値 */
    unsigned int ceil_val;            /* 切り上げた値   */
    unsigned int floor_val;           /* 切り捨てした値 */
    unsigned int nth_power = 0x0100u; /* 2の累乗, 1u << 8  */

    /* 切り捨て */
    floor_val =  val                    - (val                     % nth_power); 
    
    /* 切り上げ */
    ceil_val  = (val + (nth_power - 1)) - ((val + (nth_power - 1)) % nth_power); 
    
    printf("val       : 0x%04x.\n", val);
    printf("floor_val : 0x%04x.\n", floor_val);
    printf("ceil_val  : 0x%04x.\n", ceil_val);
    
    return 0;
}

2の累乗に合わせて最適化

上記のように剰余算を使えば切り捨て＆切り上げができます。ですが、コードサイズと処理速度的にはイマイチです。だって2の累乗なので2進数と親和性が高いんですから！つまりビット演算を使いやすいということですね！早速Ｃ言語のコードを示します。このように剰余算などの重い処理を使わずに処理できます！

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int val = 0x1234u;       /* 元の値 */
    unsigned int ceil_val;            /* 切り上げた値   */
    unsigned int floor_val;           /* 切り捨てした値 */
    unsigned int nth_power = 0x0100u; /* 2の累乗, 1u << 8  */

    /* 切り捨て */
    floor_val =  val                    & ~(nth_power - 1);     
    /* 切り上げ */
    ceil_val  = (val + (nth_power - 1)) & ~(nth_power - 1);     

    printf("val       : 0x%04x.\n", val);
    printf("floor_val : 0x%04x.\n", floor_val);
    printf("ceil_val  : 0x%04x.\n", ceil_val);
    
    return 0;
}

コードの処理内容は、ちょっと頭の体操と思って考えて見てください。慣れればどうってことはない処理です。
不明点あればコメント欄に書いていただければ、わかる範囲でお答えします！

最適化したコードとどのように差があるかは、下記の記事を参考に出力されたアセンブラを確認すると良いです。

超便利！Ｃ言語のアセンブラ出力を即確認できるサイト｜compiler-explorer

Web上ですぐにＣ言語をアセンブラ出力してくれるサイトcompiler-explorerの紹介です。複数の

hangstuck.com

まとめ

今回は2の累乗への切り上げ＆切り捨てをＣ言語で処理する方法をご紹介しました。2の累乗はビット演算と親和性が高いので、ビット演算を使い効率的なコードを書くことができます。ファームウェアではコードサイズを小さくする必要がおうおうにしてありますので、このようなテクニックも覚えていて損はないと思います。
また、10の累乗への切り上げ＆切り捨ても説明しました。こちらは剰余算を使います。こちらはご参考までに。

ちなみにこの記事は下記の本を参考にしました。