Entry

プログラミングメモ - ローテートシフトのイディオム

2009年03月24日

暇があったので,今日は新人君にお題を出して,自分もそれを解いていました。新人君がこれからやるところは符号化周りの話なので,ビット操作に慣れてもらうためにローテートシフトをば。

ローテートシフトっつのは,シフトしてあふれたビットが反対側から再び現れるシフトのこと。MD5 や SHA-1 を計算するのに必要なので,その手のライブラリでは大抵マクロになってます。実は,x86 にはローテートシフトの命令があるんですけど,ここでは C/C++ の処理系だけでやってもらうことにしました。まあ,こゆのは知ってるか知らないかの話なので,お題としてはあまり良くないんですけど……。そういえば,どう書く?org にも同じようなお題があった気がする。

#include <iostream>
#include <iomanip>

class Bit {
public:
    Bit() {
    };
    virtual ~Bit() {
    };
public:
    // 右シフト
    template<typename T>
    inline T rotateRight(T x, unsigned int n) {
        // s = n % (sizeof(T) * 8)
        unsigned int s = (n & ((sizeof(T) << 3) - 1));
        return (x >> n) | (x << ((sizeof(T) << 3) - n));
    }; 
    // 左シフト
    template<typename T>
    inline T rotateLeft(T x, unsigned int n) { 
        // s = n % (sizeof(T) * 8)
        unsigned int s = (n & ((sizeof(T) << 3) - 1));
        return (x << s) | (x >> ((sizeof(T) << 3) - s));
    };
};

int
main(int argc, char* argv[]) {
    Bit b;
    unsigned long  n1 = 0x0000000F;
    unsigned long  n2 = 0xF0000000;
    unsigned short m1 = 0x000F;
    unsigned short m2 = 0xF000;

    std::cout.setf(std::ios::hex, std::ios::basefield);
    std::cout << b.rotateRight(n1, 4) << std::endl;
    std::cout << b.rotateRight(m1, 4) << std::endl;
    std::cout << b.rotateRight(n1, 36) << std::endl;
    std::cout << b.rotateRight(m1, 36) << std::endl;

    std::cout << b.rotateLeft(n2, 4) << std::endl;
    std::cout << b.rotateLeft(m2, 4) << std::endl;
    std::cout << b.rotateLeft(n2, 36) << std::endl;
    std::cout << b.rotateLeft(m2, 36) << std::endl;

    return 0;
}

まあ……これだけなんですけど。

せっかく C++ を使ってるので,テンプレートを使って書いてみた。これで 64 bit 整数でも対応できるぜ。あとはあんまり書くことはないんですけど,そういえば新人君は,下の部分が何をやってるのかわかんね,とか言ってた。

        // s = n % (sizeof(T) * 8)
        unsigned int s = (n & ((sizeof(T) << 3) - 1));

コメントにも書いてあるんですけど,これは剰余(modulo)を取っています。シフト量がビット幅を越えると正確に計算できないので,シフト量を減らしている(32 bit 幅で 36 bit のローテートシフトは 4 bit ローテートシフトと同じ(36 ≡ 4 (mod 32)))。

で,この剰余なんですけど,2のべき(2n)の剰余なので,シフトと論理演算を使って求めています。どうしてかというと,こっちの方が速いから。コンピュータって割り算苦手なんですね。2のべきの剰余は,論理積(and)で簡単に取ることができるので,こっちを使っています。

もう少し説明すると,2n って,2進にすると,n + 1 bit 目だけに 1 が立って,n bit 以下は必ず 0 になるんですね。n bit 以下は,n bit 右シフトしたとき(2n で割ったとき)に捨てられる部分,つまり「余り」なわけで,剰余に相当します。なもんで,2n - 1 を使うと,剰余にあたるビットだけを立てたマスクとして使うことができるわけです(例:〔10進 13 を10進 8 (= 23)で割ったときの剰余〕:剰余マスクは b1000 - 1 = b0111。したがって 13 % 8 = b1101 % b1000 = b1101 & (b1000 - 1) = b1101 & b0111 = b0101 = 5)。

同様に,byte を bit に直すところも,8倍(23倍)するので,3 bit 左シフトしています。これは,高速化するときによく使う方法です。コンピュータは掛け算も苦手。

2進の演算って,工夫するといろいろできます。inline にしたのはあまり意味ねいかも。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN