frostar@wiki

メニュー

作ったもの

過去の遺物
TRPG
プログラム
リンク

自分関係

ここのページへのリンクについてはこちら
TRPGのセッション記録とかメインのブログ
生配信チャンネル。プログラム<雑談
気が向いたときにやります
個人的な質問に答えてます。

TRPG系

お世話になっているオンラインセッションサイト
TRPGのことならここ!
IRCサーバなど、お世話になってます。
ネクロニカの支援サイトです。ツール開発やオンセもやっています。

プログラム系

初心者のためのプログラムのページ。WindowsSDKの方についても詳しく書いています。
windowsSDKのテクニックがいろいろ書いてあります。
C++STL(標準テンプレートライブラリ)の日本語版リファレンスです。


更新履歴

取得中です。


CodeIQ:Bits


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題概要
法則性を見つけて文字化けしたデータを復元する。

データの先頭の一部
?0??0?0???0?000100000?11??00?0100?0??1??000001?100?0010??000?1000?001100?0001101

解法
1)区切る
ビットの羅列から法則性を見つけるのは難しいので一定個数で区切ります。
個数はビット列ということでとりあえず8bit(1バイト)で区切ってみると
?0??0?0?
??0?0001
00000?11
??00?010
0?0??1??
000001?1
00?0010?
?000?100
0?001100
?0001101
とりあえず切りよく区切れたのでこのまま進めてみることに
2)法則を見る
見ると、下に行くほど上位のビットに1が出現することが多くなっているように思えるので、このことから0からの8bitの2進数という仮定を立てます。
そこで、実際の2進数と比較すると
?0??0?0?:00000000 ○
??0?0001:00000001 ○
00000?11:00000010 ×
??00?010:00000011 ×
0?0??1??:00000100 ○
000001?1:00000101 ○
00?0010?:00000110 ×
?000?100:00000111 ×
0?001100:00001000 ×
?0001101:00001001 ×
このように当てはまらないパターンがいくつか出現するため、仮定は間違いであるとわかります。
ただし、(わかっている範囲での)最上位bitの位置が左右で一致していることから仮定と答えが近いのではないかと考えられます。
そこでとりあえず最上位の1よりも上位にある?を0にしてみます。
00000000
00000001
00000011
00000010
000001??
000001?1
0000010?
00000100
00001100
00001101
だいぶそれっぽくなってきたんじゃないでしょうか?
残るは
000001??
000001?1
0000010?
この3つですね。
最初から4つのパターンは
00000000
00000001
00000011
00000010
であるため、00→01→11→10と変化すると考えられます。
6bit目と7bit目に適用すると
0000011?
00000111
0000010?
となります。
同じものが2度出現しないことから
00000110
00000111
00000101
と決定されるため、結果は
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
00001100
00001101
となります。
ここまでくればあとはすべてに同じ法則を適用するだけです。
基本的には
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
ここまでの法則を使って上位ビットまで拡大していけばOKです。
ちなみにこれはグレイコードという2進数表記法で隣接する値のハミング距離(異なる文字の数)が常に1になるようなものです。
私は元々知ってたので上述の手順の途中で気づいてからプログラムで書き出しました。
以下がそのコードです。

public class GrayCode {
	public static void main(String args[]){
		try {
			PrintStream ps;
			ps = new PrintStream("graycode.txt");
			PrintStream oldps = System.out;
			System.setOut(ps);
			for(int i=0;i<256;i++){
				String s = Integer.toBinaryString(i^i>>1);
				s = String.format("%8s", s);
				s = s.replaceAll(" ", "0");
				System.out.println(s);
			}
			System.setOut(oldps);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}
このコードは縦に見たときのパターンからグレイコードを書き出していますので、縦のパターンから法則性に気づいた人もいるかもしれません。
ちなみに後から知ったんですが、ある2進数vからグレイコードへ変換するにはv ^ (v >> 1) をすればいいらしいです。
(^:排他的論理和、>>:ビットシフト)