2014年09月10日

C#で逆転したビット列を求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その40

■問題 (出題者:herumi さん)
32以下の正の整数nが与えられた場合に、 0以上、2のn乗未満の整数を「ビット的に逆転したもの」のリストを 作成する関数を書いてください。 なお「ビット的に逆転」とはnotを使った反転ではなく、 「0001」を「1000」にするような処理を指すものとします。
n = 4の時には [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] が正解です。
問題の理解を促すために上のリストを2進数表記で表示してみます。
0000 0
1000 8
0100 4
1100 12
0010 2
1010 10
0110 6
1110 14
0001 1
1001 9
0101 5
1101 13
0011 3
1011 11
0111 7
1111 15
n = 8などの場合のリストは音声のFFT演算でよく使わているそうです。

なかなか面白い問題ですね。
4つの方法で 書いてみました。

準備として、以下のメソッドを定義して起きます。これは、結果を2進表記で見られるようにするものです。

static string ToBinString(uint n, int fig) {           
    string s = Convert.ToString(n,2);
    return s.PadLeft(fig,'0');
}

続いて、この問題が求めている関数(PrintReverseBitListメソッド)を定義します。
このメソッドは、整数と上記 n を受け取り、反転させた整数を返す関数 revfunc を引き数で受け取っています。
PrintReverseBitListでは、revfunc を繰り返し呼び出すことで、目的の動作を実現しています。

static void PrintReverseBitList(int n, Func<uint,int, uint> revfunc) {
    for (uint i = 0; i < Math.Pow(2, n); i++) {
        Console.WriteLine("{0,3} -> {1,3}  {2} -> {3}",
            i, revfunc(i, n),
            ToBinString(i, n), ToBinString(revfunc(i, n), n));
    }
}

では、肝心の revfunc にあたるメソッドを定義しましょう。
まずは、僕がはじめに考えた力技の方法。

static uint ReverseBitNormal(uint num, int len) {
    uint mask = 1;
    uint revmask = 1u << (len-1);
    uint result = 0;
    for (int n = 0; n < len; n++) {
        if ((num & mask) == mask)
            result = result | revmask;
        mask = mask << 1;
        revmask = revmask >> 1;
    }
    return result;
}

このメソッドを先ほどの、PrintReverseBitListメソッドに以下のように渡してあげます。

PrintReverseBitList(4,ReverseBitNormal);

これを実行すれば、以下の結果を得られます。

0 ->   0  0000 -> 0000
1 ->   8  0001 -> 1000
2 ->   4  0010 -> 0100
3 ->  12  0011 -> 1100
4 ->   2  0100 -> 0010
5 ->  10  0101 -> 1010
6 ->   6  0110 -> 0110
7 ->  14  0111 -> 1110
8 ->   1  1000 -> 0001
9 ->   9  1001 -> 1001
10 ->   5  1010 -> 0101
11 ->  13  1011 -> 1101
12 ->   3  1100 -> 0011
13 ->  11  1101 -> 1011
14 ->   7  1110 -> 0111
15 ->  15  1111 -> 1111

しかし、ReverseBitNormal はプログラムのコードとしては、あまり面白味がない。

ということで、そのほかの3つの方法でも書いています。

ひとつめは、Stackを使う方法。

static uint ReverseBitStack(uint num, int len) {
    Stack<uint> stack = new Stack<uint>();
    for (int i = 0; i < len; i++ )
        stack.Push((num >> i) & 1);
    uint rev = 0;
    for (int i = 0; i < len; i++ )
        rev = rev | (stack.Pop() << i);
    return rev;
}

反転するっていえば、やはりStackですよね。
さっきと同じように、ReverseBitStack をPrintReverseBitListに渡してあげればいいですね。

PrintReverseBitList(4,ReverseBitNormal);

つぎは、再帰処理を使ったバージョン

static uint ReverseBitRecursive(uint num, int size) {
    if (size == 1)
        return num;
    uint right = ReverseBitRecursive(num >> 1, size - 1);
    uint left = (num & 1) << size - 1;
    return left | right;
}

もうちょっと簡潔にかけそうかなと思ったのですが、僕の実力はここまで。

最後は、LINQを使ったバージョン。

static uint ReverseBitLinq(uint num, int len) {
    return GetBits(num).Take(len)
                        .Select((b, i) => b << (len - i - 1))
                        .Aggregate((r, b) => r | b);
}

// 下位ビットから順に列挙する
static IEnumerable<uint> GetBits(uint num) {
    for (int i = 0; i < 32; i++) {
        yield return (num & (1u << i)) != 0 ? 1u : 0u;
    }
}

はっきり言って、これは邪道かな。後から読み直すとわけ分からなくなりそうです...



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52382363