C言語で2の累乗(2^n)への切り上げ&切り捨て

シェアする

どうも、ながやすです。

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

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

スポンサーリンク

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

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

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

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

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

#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 という変数名としてC言語で書くと、
(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の累乗と同じ式で切り捨て&切り上げができます。C言語で書くと下記のようになります。値と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進数と親和性が高いんですから!つまりビット演算を使いやすいということですね!早速C言語のコードを示します。このように剰余算などの重い処理を使わずに処理できます!

#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;
}

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

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

超便利!C言語のアセンブラ出力を即確認できるサイト|compiler-explorer
Web上ですぐにC言語をアセンブラ出力してくれるサイトcompiler-explorerの紹介です。複数の

まとめ

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