/var/crash日記: 2008-09

2008-09-25

バビリムナマコ

デイリーポータルZで干しナマコの醤油煮の記事が載ってた。
これがもうキモいのなんのって!
外面もキモいし、内臓もキモい。
実はこれは地球外生物です、と言われても信じてしまいそう。
なんかエイリアン9を思い出してしまう。

で、たまたまドルアーガの塔の小説を読み返したばかりで、「バビロニアンキャッスルサーガ」と「バビリムナマコ」のを連想したところにバビローンとか吹き出しがあって、一瞬そういうネタなのかなと思ったのだけど、別に関係なかったかな…

2008-09-02

型の最大最小値

長かった…
これがしたかっただけなんだけど、ずいぶん大げさになってしまった。

// 型の最大値
template <typename X> struct max_of {
        typedef typename SelectNegativePresentation
        <X, limits_of_u<X>, limits_of_s2<X>, limits_of_s1<X>, limits_of_sa<X>
         >::Result Selected;
        static X value() { return Selected::max(); }
};

// 型の最小値
template <typename X> struct min_of {
        typedef typename SelectNegativePresentation
        <X, limits_of_u<X>, limits_of_s2<X>, limits_of_s1<X>, limits_of_sa<X>
         >::Result Selected;
        static X value() { return Selected::min(); }
};

ちなみに、シフトによる桁あふれがあるのでg++でコンパイルするとご丁寧に警告を出してくれるのだけど、これが3000行近かったりするw

型の選択

これはLoki(というかModern C++ Design)からのパクリ。

// 型選択
// flagが真ならResultがT1、偽ならResultがT2となるクラステンプレート
template <bool flag, typename T1, typename T2> struct Select {
        typedef T1 Result;
};
template <typename T1, typename T2> struct Select<false, T1, T2> {
        typedef T2 Result;
};

// 整数の表現形式を選択する
template <typename X, typename U, typename S2, typename S1, typename SA>
struct SelectNegativePresentation {
        typedef typename Select<
                is_unsigned<X>::value, U,
                typename Select<has_sign_and_abs_part_unsafe<X>::value, SA,
                                typename Select<
                                        is_1s_complement_unsafe<X>::value, S1, S2
                                >::Result
                >::Result
        >::Result Result;
};

こいつを使うと、型の最大最小がわかるはず…

整数の表現形式ごとの最大最小

これはWikipediaを参考にしつつ。
1の補数表現と2の補数表現が同じになってしまってあれっと思ったけど、そういえば+1されてるかどうかの違いだった… 忘れてるなあ。

// 2の補数表現での最大最小
template <typename X> struct limits_of_s2 {
        static X max() { return msb<X>::value() ^ ~X(0) ; }
        static X min() { return msb<X>::value(); }
};

// 1の補数表現での最大最小
template <typename X> struct limits_of_s1 {
        static X max() { return msb<X>::value() ^ ~X(0) ; }
        static X min() { return msb<X>::value(); }
};

// 符号ビット+絶対値表現での最大最小
template <typename X> struct limits_of_sa {
        static X max() { return msb<X>::value() ^ ~X(0); }
        static X min() { return ~X(0); }
};

// 符号なし整数の最大最小
template <typename X> struct limits_of_u {
        static X max() { return ~X(0); }
        static X min() { return X(0); }
};

整数型のビット数

// Xの範囲で1 << Nが算術的に桁あふれするならvalue==1
template <typename X, unsigned N> struct arith_overflow {
        // 1<<0は算術的に桁あふれしないと定義する。
        // N>0に対しては、1<<(N-1)が算術的に桁あふれしておらず、
        // かつ(1<<N)/2 == 1<<(N-1)が成立する場合、
        // 1<<Nは算術的に桁あふれしないと定義する。
        // なお、Nビット幅の整数Xに対して(X(1)<<N)==0は必ずしも成立しない。
        enum { value = arith_overflow<X, N-1>::value
               || X(X(1) << N) / 2 != X(1) << (N - 1) };
};
template <typename X> struct arith_overflow<X, 0> {
        enum { value = 0 };     // 定義より、1<<0は算術的に桁あふれしない

};


// 整数型の有効桁のビット数を得る
template <typename X, unsigned N = 0, bool flag = false> struct valid_bits_of {
        // X(1)<<Nが桁あふれする場合(flag != false)の定義
        enum { value = N };
};
template <typename X, unsigned N> struct valid_bits_of<X, N, false>
{
        // X(1)<<Nが桁あふれしない場合(flag == false)の定義
        enum {
                // N+1〜N+3で桁あふれするか調べ、分からなければN+4で調べる
                value = arith_overflow<X, N + 1>::value ? N + 1
                : arith_overflow<X, N + 2>::value ? N + 2
                : arith_overflow<X, N + 3>::value ? N + 3
                : valid_bits_of<X, N + 4,
                arith_overflow<X, N + 4>::value>::value
        };
};


// 整数型のビット数を得る
template <typename X> struct bits_of {
        enum {
                value = valid_bits_of<X>::value + is_signed<X>::value
        };
};


// MSBのみが立った数を得る
template <typename X> struct msb {
        static X value() {
                return X(1) << (bits_of<X>::value - 1);
        }
};

valid_bits_ofで名前あってるかな?
なんで4つ飛びに調べてるかというと、Sun C++でテンプレートのネストが深すぎると警告がでたため。

符号つき数値型の表現方式判定

これは http://www.kijineko.co.jp/tech/cpptempls をまるパクリで。
ただし、クラス定義の中で静的クラス変数を定義できる処理系かちょっと思い出せなかったので、列挙定数に置き換え。
あと、符号なしの型を与えるとコンパイルエラーになるようにちょっとだけ修正。

// condが成立しない場合にコンパイルエラーにするマクロ
#define STATIC_ASSERT(cond) typedef char assertFailed[(cond) ? 1 : -1]


// 符号ありの型Xが2の補数表現ならvalue==1
template <typename X> struct is_2s_complement_unsafe {
        enum { value = (X(-1) & 3) == 3 };
};
template <typename X>
class is_2s_complement: public is_2s_complement_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

// 符号ありの型Xが1の補数表現ならvalue==1
template <typename X> struct is_1s_complement_unsafe {
        enum { value = (X(-1) & 3) == 2 };
};
template <typename X>
class is_1s_complement: public is_1s_complement_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

// 符号ありの型Xが符号ビット+絶対値表現ならvalue==1
template <typename X> struct has_sign_and_abs_part_unsafe {
        enum { value = (X(-1) & 3) == 1 };
};
template <typename X>
class has_sign_and_abs_part: public has_sign_and_abs_part_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

型の符号有無判定

http://www.kijineko.co.jp/tech/cpptempls を読んで、「numeric_limitsって便利だなあ」と感心することしきり。さっそく使ってみたい(超ミーハー)のだけど、仕事で使うとなると用意されてないかもしれない。

ということで、似たようなものをテンプレートメタプログラミングでつくれないかなと試行錯誤中。はてさて…

まずは型の符号有無をコンパイル時に判定するテンプレート。

// Xが符号つきの型ならvalue==1
template  struct is_signed {
 enum { value = 0 > X(-1) };
};

// Xが符号なしの型ならvalue==1
template  struct is_unsigned {
 enum { value = 0 < X(-1) };
};

こんな調子でいいのかな?

long longの左シフト

コンパイル時に整数型のビット数を得るテンプレートを試していて、(long long)(1ll << 64)が0にならないことに気が付いた。しかも、4294967296とかいう妙な値。

そんなわけで、検証プログラム。

#include <iostream>
int main(int argc, char *argv[]) {
        signed long long sll = 1;
        unsigned long long ull = 1;
        for(int i = 30; i < 70; i++) {
                std::cout << "1ll<<" << i << " = " << (sll << i)
                          << "\t1ull<<" << i << " = " << (ull << i)
                          << std::endl;
        }
        return 0;
}

Sun C++でコンパイルして実行してみると


1ll<<60 = 1152921504606846976     1ull<<60 = 1152921504606846976
1ll<<61 = 2305843009213693952     1ull<<61 = 2305843009213693952
1ll<<62 = 4611686018427387904     1ull<<62 = 4611686018427387904
1ll<<63 = -9223372036854775808    1ull<<63 = 9223372036854775808
1ll<<64 = 4294967296      1ull<<64 = 4294967296
1ll<<65 = 8589934592      1ull<<65 = 8589934592
1ll<<66 = 17179869184     1ull<<66 = 17179869184
1ll<<67 = 34359738368     1ull<<67 = 34359738368
1ll<<68 = 68719476736     1ull<<68 = 68719476736
1ll<<69 = 137438953472    1ull<<69 = 137438953472

g++でコンパイルして実行してみると

1ll<<60 = 1152921504606846976     1ull<<60 = 1152921504606846976
1ll<<61 = 2305843009213693952     1ull<<61 = 2305843009213693952
1ll<<62 = 4611686018427387904     1ull<<62 = 4611686018427387904
1ll<<63 = -9223372036854775808    1ull<<63 = 9223372036854775808
1ll<<64 = 1       1ull<<64 = 1
1ll<<65 = 2       1ull<<65 = 2
1ll<<66 = 4       1ull<<66 = 4
1ll<<67 = 8       1ull<<67 = 8
1ll<<68 = 16      1ull<<68 = 16
1ll<<69 = 32      1ull<<69 = 32

CPUはいずれもAMD Opteron。コンパイラのバージョンは


CC: Sun C++ 5.7 Patch 117831-02 2005/03/30
g++ (GCC) 3.4.3 (csl-sol210-3_4-branch+sol_rpath)

まあ、ビット幅を越えてシフトした場合の振る舞いは未定義だった気がするので、その意味ではおかしくはない。けど、コンパイラによって振る舞いが違うってのはちょっと意外だったなあ。

けど、ビット幅Nの型Xに対して常に(X)(X(1)<<N)==0が成立するとばかり思い込んでいたので、ちょっと期待が外れてしまったりして。

たらいまわし関数その2

さきのテンプレート版たらい回し関数(関数じゃないけど)、どうもおかしいと思ったら>と<がHTMLタグ扱いになってた… はずかしー

ちなみにg++のバージョンはg++ (GCC) 3.4.3 (csl-sol210-3_4-branch+sol_rpath)。ちょっと古いかもしれないので、4.xでは改良されているかもしれない。

で、今度はSun C++で挑戦。

% CC -V
CC: Sun C++ 5.7 Patch 117831-02 2005/03/30
% time CC tarai_t.cc
7.08u 0.17s 0:07.49 96.7%
% ./a.out
Tarai(384, 192, 0) = 384

これもかなり古いけど、意外とあっさりと成功。

2008-09-01

テンプレート版たらいまわし関数

Modern C++ Designなど読んでしまったもので、たらいまわし関数をコンパイル時に計算しようと思い立つ。

template <bool flag, typename T1, typename T2> struct Select {
 typedef T1 Result;
};

template <typename T1, typename T2> struct Select<false, T1, T2> {
 typedef T2 Result;
};

template <int x, int y, int z> struct Tarai;

template <int x, int y, int z> struct Tarai1 {
 enum { value = y };
};

template <int x, int y, int z> struct Tarai2 {
 enum { value = Tarai<
    Tarai<x-1,y,z>::value,
    Tarai<y-1,z,x>::value,
    Tarai<z-1,x,y>::value
        >::value };
};

template <int x, int y, int z>
struct Tarai {
 typedef Select< (x <= y), Tarai1<x, y, z>, Tarai2<x, y, z> > Selected;
 enum { value = Selected::Result::value };
};

#include <iostream>

int main()
{
 //enum { x = 768, y = 384, z = 0 };
 enum { x = 384, y = 192, z = 0 };
 std::cout << "Tarai(" << x << ", " << y << ", " << z << ") = " << Tarai<x,y,z>::value << std::endl;
}

こんなものかな。しかし、テンプレートメタプログラミングはコンパイラのエラーを理解するのが大変だなあ…

% time g++ -ftemplate-depth-8000 tarai_t.cc
virtual memory exhausted: 資源が一時的に使用できません。
1215.41u 3.25s 22:23.57 90.7%

(´・ω・`)ｼｮﾎﾞｰﾝ

登録: 投稿 (Atom)

/var/crash日記

2008-09-25

バビリムナマコ

2008-09-02

型の最大最小値

型の選択

整数の表現形式ごとの最大最小

整数型のビット数

符号つき数値型の表現方式判定

型の符号有無判定

long longの左シフト

たらいまわし関数その2

2008-09-01

テンプレート版たらいまわし関数

ラベル

ブログアーカイブ

自己紹介

2008-09-25

2008-09-02

2008-09-01

ラベル

ブログ アーカイブ

自己紹介

ブログアーカイブ