【トリッキーなコード】剰余演算(mod)をトリッキーに

呼ばれて飛び出てジャジャジャジャーン！！
え～っと、ちょっと遊び心満載の話題を提供してみます (*￣ー￣*)

下のコードを見てください。
int func(int num)
{
    while (num >= 14)
        num = (num >> 3) + (num & 7);

    if (num >= 7)
        num -= 7 ;

    return num;
}
funcという名前の関数が一つ定義されていますが、
このfunc関数、一体何をする関数か分かりますか？？




・・・といっても、これがパッと分かる人なんてそうそういないと思うので、
答えを言っちゃいますと、
実はこれ、mod 7 を求める関数です。


うっそ～～、信じらんな～い！！という人の為に、一応検証してみます。


剰余演算(mod)の関数を自作（C言語）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int mod7(int num)
{
    while (num >= 14)
        num = (num >> 3) + (num & 7);

    if (num >= 7)
        num -= 7 ;

    return num;
}

int main(void)
{
    int i,num;
    srand ((unsigned int)time(NULL));

    for (i=0; i<10; i++) {
        num = rand();
        printf("% 6d => %d - %d\n", num, num % 7, mod7(num));
    }
    return 0;
}
ランダムな整数を作成し、%演算子を使ってmod 7を行った値と、冒頭の関数の戻り値を比較するコードです。

↓↓ 実行結果は以下のとおり ↓↓

はい、mod 7を求める関数が正常に動作しているのが確認できました～＾＾；）


さてさて、この関数を眺めていると、
mod 7以外の剰余演算もできそうだな～という気がしますよね？？

というわけで、改良を加えたのが以下のコードです。


剰余演算(mod)の関数を自作２（C言語）
int modX(int num, int nMod, int nBit)
{
    while (num >= nMod * 2)
        num = (num >> nBit) + (num & nMod);

    if (num >= nMod)
        num -= nMod;

    return num;
}

int main(void)
{
    int i, num, nMod, nTmp, nBit;
    srand((unsigned int)time(NULL));

    // 剰余演算する数を設定
    nMod = 15;

    nBit = 1;
    nTmp = nMod;

    while (nTmp >>= 1)
        nBit++;

    for (i=0; i<10; i++) {
        num = rand();
        printf("% 6d => [% 3d] - [% 3d]\n", num, num % 15, modX(num, 15, nBit));
    }

    return 0;
}
modX関数の、引数 num には剰余演算される数、nMod には剰余演算する数を入れます (第3引数のnBitに関しては後述します）。
すると、あ～ら不思議、%演算子を使わなくても、剰余演算した結果を取得することができてしまいます！

↓↓ 実行結果はご覧のとおり（ここでは mod 15を計算してみました）↓↓

はい、正常に動作していますね＾＾；）


さて、ではmodX関数の第3引数(nBit)についてです。
nBitには、剰余演算する数(nMod)を表示する為に必要な、最小bit数を入れます。

main関数内の
nBit = 1;
nTmp = nMod;

while (nTmp >>= 1)
    nBit++;
の部分で、ここで紹介した小技を使用し、bit数を計算しています。



・・・では最後に、このmodX関数の最も重要なポイント（欠点ともいうｗ）をご紹介しておきます。
それは、剰余演算する数(nMod)に入れる事のできる数値が決まっている ということです(爆)

小さい数から順に、7, 15, 31, 63, 127, ...
つまり、特定のbit数で表すことのできる最大値じゃないと、mod値を計算できません＾＾；）

さらに、関数内の処理の大半がbit演算だから、実行速度ぐらいは速いんじゃないかな～～？？
と考えて、処理時間を計測してみたんですが、%演算子を使って処理を行った方が、実行速度が速かったです＾＾；）

ついでに、すでにお気づきの方も多いでしょうが、この関数はマイナス値が全く考慮されていません♪


というわけで、長々と書きましたが、
このネタは「多人数プロジェクトで意図的にコードの可読性を下げて嫌がらせをする」以外は、おそらく何も利点がないと思われます＾＾；）

ここまでお付き合い下さり、

ほ　ん　と　う　に　あ　り　が　と　う　ご　ざ　い　ま　し　た　ｗ