frostar@wiki
CodeIQ:Bits
最終更新：
frostar
-
view
- 問題概要
- 法則性を見つけて文字化けしたデータを復元する。
- データの先頭の一部
- ?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) をすればいいらしいです。
(^:排他的論理和、>>:ビットシフト)
ちなみに後から知ったんですが、ある2進数vからグレイコードへ変換するにはv ^ (v >> 1) をすればいいらしいです。
(^:排他的論理和、>>:ビットシフト)
[Amazon商品]
