トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> トリッキーなコード >> 剰余演算(mod)をトリッキーに

特定の剰余演算(mod)をトリッキーに行う方法

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

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

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

    return num;
}
funcという名前の関数が一つ定義されていますが、 このfunc関数、一体何をする関数か分かりますか??      ____    ━┓    /      \   ┏┛   /  \   ,_\.  ・ /    (●)゛ (●) \ |  ∪   (__人__)    | /     ∩ノ ⊃  / (  \ / _ノ |  | .\ “  /__|  |   \ /___ / ・・・といっても、これがパッと分かる人なんてそうそういないと思うので、 答えを言っちゃいますと、 実はこれ、mod 7 を求める関数です。 うっそ~~、信じらんな~い!!という人の為に、一応検証してみます。

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)関数の結果 はい、mod 7を求める関数が正常に動作しているのが確認できました~^^;) さてさて、この関数を眺めていると、 mod 7以外の剰余演算もできそうだな~という気がしますよね?? というわけで、改良を加えたのが以下のコードです。

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を計算してみました)↓↓ 自作剰余演算(mod)関数の結果-2 はい、正常に動作していますね^^;) さて、ではmodX関数の第3引数(nBit)についてです。 nBitには、剰余演算する数(nMod)を表示する為に必要な、最小bit数を入れます。 main関数内の
nBit = 1;
nTmp = nMod;

while (nTmp >>= 1)
    nBit++;
の部分で、ここで紹介した小技を使用し、bit数を計算しています。 ・・・では最後に、このmodX関数の最も重要なポイント(欠点ともいうw)をご紹介しておきます。 それは、剰余演算する数(nMod)に入れる事のできる数値が決まっているということです(爆) 小さい数から順に、7, 15, 31, 63, 127, ... つまり、特定のbit数で表すことのできる最大値じゃないと、mod値を計算できません^^;) さらに、関数内の処理の大半がbit演算だから、実行速度ぐらいは速いんじゃないかな~~?? と考えて、処理時間を計測してみたんですが、%演算子を使って処理を行った方が、実行速度が速かったです^^;) ついでに、すでにお気づきの方も多いでしょうが、この関数はマイナス値が全く考慮されていません♪ というわけで、長々と書きましたが、このネタはおそらく何も利点がないと思われます^^;) ここまでお付き合い下さり、 ほ ん と う に あ り が と う ご ざ い ま し た w
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。