8x8のビット行列を転置する

@Nabetani さんが主催されてい「オフラインリアルタイムどう書く」のシリーズ。
3月まではオンラインで投稿させてもらっていたのですが、4月以降いろいろと余裕がなくなってしまい、すっかり遠のいてしまっていました。

なのですが。なにやら参加のラブコールがあったらしいというのを耳にしたのと、偶然にも会社の同僚が前回のどう書くに参加していたのというのが相まって、どうにか書きたい欲が復活してきました。

しかし、会社で「どう書く」でわたしの名前が出ていたとその同僚から聞いたときは挙動不審になってしまいましたよ。どこでどうつながっているのやら、エンジニアのネットワーク、あなどりがたし。

閑話休題。

• 問題の方 : 第16回オフラインリアルタイムどう書くの問題 - Qiita
• わたしが解いたの : 第16回オフラインリアルタイムどう書く C++で - Qiita

Rubyエンジニアになったにもかかわらず、いまだにC++が自分の中では主力兵器なのだと実感したところ。

転置

今回、縦方向と横方向とで数を数えることになるのですが、普通に考えれば、そのままの状態で横方向に数えて、転置して横方向に数えて、とすればよいようです。
みなさんの解答を見ても、転置メソッドが標準で用意されている言語、例えばRubyでは[http://docs.ruby-lang.org/ja/2.0.0/method/Array/i/transpose.html:title=Array::transpose]メソッドなどを利用している例が多くありました。

C++では標準ではそんなものはありません。
が、しかし。今回はビット行列です。ビット操作です。
ビット操作と言えば。「ハッカーのたのしみ」。

本文中ではレジスタ長が32ビットとして書かれているのですが、時代は64ビット。
と、いうことで。64ビット版にして書き直してみました。

#include <cstdint>

uint64_t transpose8(uint64_t x)
{
    uint64_t t = (x ^ (x >> 7)) & 0x00aa00aa00aa00aa;
    x = x ^ t ^ (t << 7);
    t = (x ^ (x >> 14)) & 0x0000cccc0000cccc;
    x = x ^ t ^ (t << 14);
    t = (x ^ (x >> 28)) & 0x00000000f0f0f0f0;
    x = x ^ t ^ (t << 28);
    return x;
}

#include <iostream>
#include <iomanip>

int main(int, char* [])
{
    uint64_t x = 0x00102828447c8282;

    std::cout
        << std::hex << std::setfill('0')
        << std::setw(16) << x << '\n'
        << std::setw(16) << transpose8(x) << std::endl;
    return 0;
}

昔なつかしの8ビットフォントを転置します。
元のデータ。

00000000 00
00010000 10
00101000 28
00101000 28
01000100 44
01111100 7c
10000010 82
10000010 82

これが、こうなります。

00000011 03
00001100 0c
00110100 34
01000100 44
00110100 34
00001100 0c
00000011 03
00000000 00

実行結果。

$ ./a.out
00102828447c8282
030c3444340c0300

（追記：データが間違っていたのでちっと修正）

今回のどう書くでは6x6ビットのビット行列ですが、そのばあいでもシフトする量とマスクを調節することで対応することができます。
6x6ビットのビット行列を転置する方法で書き換えたのがこちらです。

いつか読むはずっと読まない：ハッカーはプログラミングを楽しむ

今回、リンクを作るためにこの本をamazon.co.jpで検索したんですが。「お客様は、2006/2/5にこの商品を注文しました。」と表示されまして。ずいぶん時間がたったんだなぁと思うと同時に、今回ビット操作をするときにすぐに思い出したのがこの本で、中身の詳細まではともかくとしても一度覚えたことは本当に忘れないものだなぁと思った次第。
中身の詳細はすっかり頭から抜けていたけれど orz。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか