2014年09月17日

C#でバイナリークロック

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

■問題 (lunlumo さん)
時刻を二進数相当の表現で出力する時計アプリケーションを書いてください。
20:18の場合,例えば以下の様な出力をするイメージです。

出力例:
■□■□□
□■□□■□

参考: Binary Clock Widget http://www.android-app.info/2009/07/01/binary-clock-widget/

コンソールアプリケーションとして作成。
起動すると、1秒おきに表示が切り替わります。

せっかくなので、時分秒を表示するようにしてみました。
BinaryClockクラス自体は、コンソールアプリケーションに依存していないので WindowsFormsアプリでも、WPFアプリでも利用できます。

BinaryClockのコンストラクタで指定する Action デリゲートで 実際の表示を行います。
Action デリゲート(このコードでは、Printメソッド)は、1秒ごとに呼び出されます。

Printメソッド内では、Console.SetCursorPositionで表示位置を固定しているので、 コンソール画面が流れることはありません。

using System;
using System.Linq;

namespace Doukaku.Org {

    class Program {
        static void Main(string[] args) {
            Program app = new Program();
            app.StartBinClock();
            // Enterキーが押されるまで、時刻を更新し続ける。
            Console.ReadLine();
            app.StopBinClock();
            Console.ReadLine();
        }

        private int left;
        private int top;

        BinaryClock binaryClock;

        public Program() {
            left = Console.CursorLeft;
            top = Console.CursorTop;
        }

        private void StartBinClock() {
            binaryClock = new BinaryClock(Print);
            binaryClock.Start();
        }

        private void StopBinClock() {
            binaryClock.Stop();
        }

        private void Print(string[] lines) {
            Console.SetCursorPosition(left, top);
            Console.WriteLine(lines[0]);
            Console.WriteLine(lines[1]);
            Console.WriteLine(lines[2]);
        }
    }

    // コンソールアプリケーションとして作成
    // 秒も表示するようにしてみた。
    public class BinaryClock {
        public BinaryClock(Action<string[]> action) {
            this.action = action;
        }

        private System.Timers.Timer timer = new System.Timers.Timer();
        private Action<string[]> action;

        public void Start() {
            timer.Interval = 1000;
            timer.Elapsed += timer_Elapsed;
            timer.Start();
        }

        public void Stop() {
            timer.Stop();
        }

       private  void timer_Elapsed(object sender, System.Timers.ElapsedEventArgs e) {
            DateTime now = DateTime.Now;
            var lines = new string[] {
                HorToString(now),
                MinuteToString(now),
                SecondToString(now),
            };
            action(lines);
        }

        private static string ToBinString(int num, int width) {
            string format = string.Format("{{0,{0}}}", width);
            string s = String.Format(format,
                                     System.Convert.ToString(num, 2));
            return s.Replace('1', '■').Replace('0', '□').Replace(' ', ' ');
        }

        private string HorToString(DateTime dateTime) {
            return ToBinString(dateTime.Hour, 6);
        }
        private string MinuteToString(DateTime dateTime) {
            return ToBinString(dateTime.Minute, 6);
        }
        private string SecondToString(DateTime dateTime) {
            return ToBinString(dateTime.Second, 6);
        }
    }
}

  

Posted by gushwell at 22:30Comments(0)TrackBack(0)

2014年09月14日

C#で2進数の記述を容易に

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

■問題 (出題者:yappy さん)
コンピューターの原理は2進数だというのに、多くのプログラミング言語で8進数や16進数しか記述できないのは少し変だとは思いませんか?
そこで、ソース中に2進数を定数として書く方法、またはその代替手段を考えてください。

ある程度の評価基準を示します(できるところまでで構いません)。
・2進数の表示方法は0と1 
・桁数は可変長 
・コンパイル等の後に最適化等によって定数に変換されることが見込まれる 
Cで関数として実装したものを示しておきます。
1
2
3
4
5

int bin(int b1, int b2, int b3, int b4, int b5, int b6, int b7, int b8){
    return b1<<7 | b2 <<6 | b3<<5 | b4<<4 | b5<<3 | b6<<2 | b7<<1 | b8;}

int byte = bin(0, 1, 1, 0, 1, 0, 0, 1);


上記問題の3つ目の基準は無視します。
Convert.Int32, Convert.ToString() を使えば、文字列からintへ、intから文字列への変換は 簡単に行えるのですが、せっかくなので、C#らしくBinaryNumberという構造体を作成。
演算子のオーバーロード、暗黙の型変換、明示的な型変換などの機能を利用しています。
文字列からBinarryNumberへの変換はもちろん、int と BinarryNumberとの相互変換が可能。
使い方は、コードのMainメソッドを見てください。

using System;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var bn1 = new BinaryNumber("010101");
            var bn2 = (BinaryNumber)"1111";    //明示的な型変換 
// string -> BinaryNumber BinaryNumber bn3 = bn1 + bn2; //演算子+のオーバーロードで実現 Console.WriteLine(bn3); //暗黙の型変換
// BinaryNumber -> int Console.WriteLine(bn3.ToString()); //ToString()のoverload int n1 = bn1; //暗黙の型変換
// BinaryNumber -> int int n2 = (int)bn2; //明示的な型変換
// int -> BinaryNumber int n3 = n1 + n2; Console.WriteLine(n3); BinaryNumber bn4 = new BinaryNumber(32); var n4 = n3 - bn4; //暗黙の型変換
// BinaryNumber -> int Console.WriteLine(n4); Console.ReadLine(); } } struct BinaryNumber { private int _num; public BinaryNumber(int num) { _num = num; } public BinaryNumber(string s) { _num = Convert.ToInt32(s, 2); } public static implicit operator int(BinaryNumber bn) { return bn._num; } public static explicit operator BinaryNumber(int n) { return new BinaryNumber(n); } public static explicit operator BinaryNumber(string s) { return new BinaryNumber(s); } public static BinaryNumber operator +(BinaryNumber b1, BinaryNumber b2) { return new BinaryNumber((int)b1 + (int)b2); } public static BinaryNumber operator -(BinaryNumber b1, BinaryNumber b2) { return new BinaryNumber((int)b1 - (int)b2); } public static BinaryNumber operator *(BinaryNumber b1, BinaryNumber b2) { return new BinaryNumber((int)b1 * (int)b2); } public static BinaryNumber operator /(BinaryNumber b1, BinaryNumber b2) { return new BinaryNumber((int)b1 / (int)b2); } public override string ToString() { return Convert.ToString(_num, 2); } } }
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

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;
    }
}

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

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

2014年09月07日

C#でビットのローテートシフト

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

■問題 (出題者:ところてん さん)
ローテートシフトを実装してください。
例)
0010 0011 1110 1101
↓右に1ビットローテート
1001 0001 1111 0110
ローテートシフトがある言語がどれ位あるか知りたくなって投稿しました。

たぶん、C#には、ローテートシフトはないと思うので、自分でゴリゴリ書くしかなさそうですね。
int限定ですが、マイナスの時にも正しくシフトするように書いてみました。
そのために、intをむりやりuintにキャストしています。

RotateBitメソッドの第二引数は、シフトする数を指定します。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            unchecked {
                int n = (int)0x8106041d;
                Print(n);
                Print(RotateBit(n, 1));
                Print(RotateBit(n, 2));
                Print(RotateBit(n, 3));
                Print(RotateBit(n, 4));
                Print(RotateBit(n, 5));
                Print(RotateBit(n, 6));
            }
            Console.ReadLine();
        }

        static int RotateBit(int value, short n) {
            return (int)(((uint)value >> n)
                        | ((uint)value << (32 - n)));
        }
        static IEnumerable<int> GetBits(int n) {
            for (uint i = 0x80000000; i != 0; i >>= 1) {
                yield return (n & i) != 0 ? 1 : 0;
            }
        }

        static void Print(int n) {
            GetBits(n)
                .Select((m, i) => ((i % 4) == 3) ? m.ToString() + " " : m.ToString())
                .ForEach(x => Console.Write(x));
            Console.WriteLine();
        }
    }

}

  
Posted by gushwell at 23:00Comments(0)TrackBack(0)