2015-12-29

XORの使用例

はじめに

みなさんはXOR(eXclusive OR, 排他的論理和)を使っているでしょうか？排他的論理和は論理演算の中でも難しいと言われているので難しく感じるかもしれませんが、すごく応用が利きます。

XOR

XORは入力をx, yとしたとき、xとyが同一なら0、違えば1を出力します。

x	y	結果
0	0	0
0	1	1
1	0	1
1	1	1

XORの特性として、2回同じ値でXORをとると元に戻ります。
例:

01101
10101
------
11000 ←1回目の計算結果
10101
------
01101 ←2回目の計算結果

また、x ^ y = zのとき、x ^ z = yとy ^ z = xを満たします。

使用例

使用例を見ていきましょう。

チェックサム

データが正しいかどうか調べるときに、一定の長さごとにXORをとって、全て0ならば、そのデータは正しいと言えます。

XOR交換

XORを用いることにより、一時変数を用いずに値の交換が可能です。 x ^ y = zならばx ^ z = yとy ^ z = xを利用しています。

x = x ^ y;
y = x ^ y;
x = x ^ y;

1行目でxにx ^ y、つまりzが代入されます。
2行目でyにz ^ y、つまりxが、3行目でxにz ^ x、つまりyが代入されることになります。
一時変数を使わないのでメモリを節約できますが、CPUなどによっては一時変数を用いたほうが早いことがあるようです。

XOR暗号

2回同じ値でXORをとることで元に戻る特性を利用することにより、暗号鍵と復号鍵が同一な暗号を作成できます。
単一換字式暗号で暗号強度はとても弱いですが、非常に簡単に実装できます。

Xorshift

Xorshiftは擬似乱数生成アルゴリズムの一種で、実装が簡単で、高速です。
wikipediaに実装例が載っているのでそちらをどうぞ。

最後に

XORは非常に単純ながら、様々なことに応用できます。
論理回路を学んだとき、XORは便利と聞いて、何が便利なのか疑問に思っていましたが、実際便利です。
もしかすると、将来の技術もXORを利用する技術かもしれません。

2015-12-07

日本語プログラミング言語なでしこ

この記事はSLP KBIT Advent Calendar 2015 - Adventarの7日目の記事です。

なでしこについて

なでしこはクジラ飛行机氏によって作られたインタプリタ方式のスクリプタ言語です。この言語の最大の特徴は日本語でプログラミングができるということです。
ダウンロードは次のサイト(http://nadesi.com/top/)からできます。ダウンロードをしてすぐに使えます。

日本語プログラミング

大抵のプログラミング言語はアルファベットで記述します。日本語が使えるのはコメント、文字列、変数(Javaなど一部の言語)ぐらいでしょう。
日本語でプログラミングできるのはなでしこ、ひまわり、ドリトル、Mind、プロデル、Prolog(一部の処理系のみ)ぐらいであまりありません。~~トミー・・・ぴゅう太・・・頭の中で何かが~~

日本語プログラミング言語が少ない理由として、字句解析が難しいことがあります。ひまわりでは、読点やスペースで字句を区切らないといけないです。なでしこでは、助詞区切りを用いることにより自然に近い日本語で記述することが可能です。(「こんにちは」が「こんにちは」と区切られるという問題があったりしますが)

日本語プログラミングの利点は何でしょうか？それは日本語圏の人が直感的にプログラミングできることでしょう。アルファベットを用いてプログラミングをするとき、日本語から英語に変換する必要があります。日本語プログラミングではその手順が必要ないのです。~~英語の方がわかりやすいとか言わない~~

書き方

なでしこは日本語プログラミング言語なので演算子等は全角でも可能です。

hello world

手始めにhello worldをしてみましょう。

「こんにちは、世界」と言う。

メッセージボックスが出ます。

こんなことも出来ます。

クジラが「こんにちは、世界」と言う。

クジラが「こんにちは、世界」と言いましたね。このように、なでしこはGUIが作りやすいです。

変数

変数は文字列、整数、数値、配列、ハッシュの型があります。動的型付けになっています。型宣言は

aとは変数。

と書き、変数宣言は

aは10
a = 10
10をaに代入。

の3種類があります。

四則演算

四則演算は演算子を使えますし、日本語で書くことも可能です。

aは10と5を足したもの
aは10と5の和
a = 10 + 5

条件分岐

条件分岐は、もし(if)、ならば(then)、違えば(else)を使います。

もし、aが10以上ならば
    「aは10以上」と表示する。
違えば、
    「aは10より小さい」と表示する。

繰り返し

n回繰り返したいときは、

n回
    (処理)

Cのfor文のようにカウンタで繰り返したいときは、

iで0から9まで繰り返す
    (処理)

while文のように条件が真の間繰り返したいときは、

iが9以下の間
    (処理)

配列

配列のアクセスは、

a￥0
a[0]

の2種類です。多次元配列は、

a￥0,1
a[0,1]

です。

ハッシュ

ハッシュは

香川＠「うどん」は「さぬきうどん」
香川＠「県庁所在地」は「高松市」

と書きます。マニュアルによると"@"は日本語の「の」に似ているからとのことです。

最後に

なでしこは文系サラリーマンのために役立つ言語と言われるように、MS Officeなどでの仕事の効率化を図ることができます。
もちろんそれ以外も可能で、様々なアプリケーションを作ることが可能です。
日本語のみで書けるので、英語がわからない人でも簡単にプログラミングを行うことができると思います。僕が最初に触れたプログラミング言語はひまわりでした。
今のなでしこはWindowsでのみ動きますが、現在開発されているなでしこ2.0ではC#で書かれているので、MacやLinuxでも動くようになります。楽しみですね。

2015-10-25

CODE FESTIVAL 2015 予選B

A問題とB問題はRuby、C問題はC++で解いています ※おそらく参考になりません

A問題

A問題は入力された文字を全て含むような小文字アルファベットのみからなるダブル文字列を出力する問題なのですが、どういうわけかこれでACになりました。(Ruby)

s = gets.split
printf("%s%s%s%s\n", s[0], s[1], s[0], s[1])

なぜこれを書いたのか自分でも理解に苦しみますが、とりあえずsには要素数1で0番目に改行を除いた文字列が入っていることになっていて、 printfのs[1]は無視されて偶然ACになったと思います。

B問題

B問題は数字が出てきた回数が出てきてそれが総数の半分を超えるならばその数字を出力し、そうでなければ'?'を出力する問題です。どうすればいいのかわかっていたはずなのですが、indexメソッドをど忘れしていたので添字を出せず悩みました。

C問題

C問題は降順にソートして終わり！

D問題

わかりませんでした。

まとめ

順位は382位でした。 B問題で躓かなければもっと上だったと思います。

2015-09-27

CODE FESTIVAL 2015 予選A

はじめに

みなさんはCODE FESTIVAL 2014をご存知でしょうか？
CODE FESTIVAL(以下CF)2014は、おそらく世界初のフェス型のプログラミングコンテストです。
プロコンガチ勢でも、プログラミングの経験が浅い人でも、参加者全員が楽しめるプロコンでした。
僕はCFには参加できませんでしたが、日帰りイベントのCODE THANKS FESTIVAL 2014に参加できました。
CODE THANKS FESTIVAL(以下CTF)の感想は叙々苑の焼肉弁当です。(CTFも交通費が支給されました)
今年もCODE FESTIVAL 2015が開催されます。

予選A

2015年9月26日21:00～23:00、CF2015の予選Aが開催されました。
結果は3問完答、514位でした。
使用言語はC++です。

A問題

「大文字アルファベット+"2014"」の文字列を「大文字アルファベット+"2015"」に書き換える問題です。
基本的にA問題はif文で分岐する、もしくはただ出力するだけといった簡単な問題が出題されるのですが、今回の問題は難しかったです。

B問題

数列に含まれる数の和を求める問題です。
数列の規則性を発見すれば解くことができると思います。

C問題

指定時間内に終わらせるために必要な時間短縮の回数を求める問題です。
はじめにバブルソートで実装してみたところ、プログラムが時間内に終わりませんでした。
次にクイックソートで実装してみたところ、配列の要素が重複するとバグが発生しました。
~~重複をどうにかするほどプログラミングが出来ないので~~時間がないので、stdlib.hのqsort関数を用いました。

D問題

D問題の例に漏れず難問です。
解けませんでした。

まとめ

昨年のCF2014予選Bでは2問完答+部分点だったので、昨年よりも成長したと思います。
今年の参加者はレベルの高い方が多いと思います。~~みんな叙々苑の焼肉弁当が好きなんですね~~
ガチな人が多くて驚きましたが、このプロコンの目的は楽しむことです。
予選でも楽しめたらいいと思っています。
10月25日に予選Bがありますので楽しみたい方は是非とも参加してください。
~~焼肉弁当食べたいからCTFの参加条件緩くしてくださいお願いします~~

2015-07-20

MacBookAir11インチ購入

Mac

はじめに

先日(2週間前)いつも使っているPCが壊れた。
所謂生協PCで、アカデミックサポートを受けていたので代替機を貸してもらったが、
ボロボロなうえに、(スペックはそんなに悪くないのに)やたら固まる。
ここで、サブPCが欲しいと思った。

迷い

サブPCが欲しいと思ったが、どれにすればいいのか迷った。
選択肢としては格安ノート、Winタブ、そしてMacBookである。
必要な機能は、

Officeが使える
プログラミングをしやすい
持ち運びやすい
Flash対応

である。 ~~Flash対応というのは艦これがやりたいから~~
あとは何か機能(タッチパネルなど)が欲しい。
格安ノートには特に機能がないので選択肢から外れる。
WinタブかMacBookかをまわりに聞いてみると圧倒的にMacBookを推されたので、
MacBookProを検討したが、そんなに予算はない。
よってWinタブを検討した。
Winタブを検討しながら今日まで日が過ぎた…。

意識レベルMAX

今日、なぜか意識高いことを熟考していた。正直自分でも意味がわからない。
所謂意識高い人はMacBookを使っている傾向があるので、また迷いだす。
そしてふとツイートをしたところ…

MacBookユーザの夜の夢

@moxtsuan Macbookですね
— さるる (@wakatakeru) 2015, 7月 20

ここからMacBookユーザによる勧誘がはじまったのだ！(半分嘘)
意識高いことを熟考していたのは、~~電波を受信していたから~~きっとMacBookと縁があるのだろうとMacBookについて熟考する。
まず僕がMacBookに求めていたことはオールインワンだったのだが、サブPCだと割り切れば、そんな必要はないと考えた。
サブPCとしてMacBookを検討した結果、MacBookAir11インチが物理的にも価格的にも最適だという結論を得た。
思い立ったが吉日と早速AppleストアでMacBookAirを購入。Corei7、メモリ8GB、US配列のカスタマイズをした。
ちょうどローンの利率が1%だったのも幸いだった。(0%だともっとよかったのだが)
ちなみにローンが通るかどうかは今日(2015/07/20)の段階では不明なので、通らなかったらつらい。

最後に

ローンが通れば1週間以内にMacデビューできるので、とても楽しみ。
MacはC#も、なでしこも、使えないのはちょっと…と思っているが、UNIXなのでハッカーライフを楽しめそうだ。
(2015.07.27 追記)Mac届きました。

2015-05-10

スタック領域

コンパイラ

某プロコンで巨大な配列が必要(だと感じた)になった。

int array[100000][100000];

これでコンパイルするとコンパイルは出来るが、実行できない。
もしかしてWindowsがイカれてしまったのかと思い、これからは静的メモリ確保ではなく動的メモリ確保で生きていこうと思っていたが、調べてみるとスタック領域という領域があるようである。
スタック領域とはざっくり言えば関数のスタックや自動変数を格納しておく領域のことである。(多分)
スタック領域はとても小さく、調べてみたところ自分の環境では約2MBほどだと思われる(gcc4.8.1)。
これをどうにかするにはstaticもしくはグローバル変数として宣言することによって静的領域に格納させる、動的確保で配列を作ることが挙げられる。
ちなみにこの問題ではr行c列ということになっていたので、GCCでは

int r, c;
scanf("%d %d", &r, &c);
int array[r][c];

も可能である。

2015-03-05

C#始めてみた

C#始めてみた。
一応CとC++とJavaとRubyの経験がある(C++はbetterC、JavaはFizzBuzz程度だが)のですぐに出来るかなと思っていたがコンストラクタの継承あたりで躓いている。

class Cicken
{
    protected bool sex;
    public Cicken(bool Csex)
    {
        sex = Csex;
    }
    public void Voice()
    {
        System.Console.WriteLine("???");
    }
    public void Sex()
    {
        if (sex)
        {
            System.Console.WriteLine("female");
        }
        else
        {
            System.Console.WriteLine("male");
        }
    }
}

class Egg : Cicken
{
    public string state;
    public Egg(bool Csex)
    {
        state = "egg";
    }
    new public void Voice()
    {
        System.Console.WriteLine("korokoro");
    }
}

class Test
{
    static void Main()
    {
        Cicken cicken = new Cicken(true);
        Egg egg = new Egg(false);

        cicken.Voice();
        cicken.Sex();
        egg.Voice();
        egg.Sex();
    }
}

これをビルドしようとすると「'Cicken'に引数を 0 個指定できるコンストラクターがありません」というエラーが出る。
どうやら子クラスのコンストラクタ呼び出しの直前に親クラスの引数0個のコンストラクタを呼び出すかららしい。
そういう時は子クラスのコンストラクタを

Ko(int fuga) : base(fuga){ ... }

とすればいいらしい。

class Cicken
{
    protected bool sex;
    public Cicken(bool Csex)
    {
        sex = Csex;
    }
    public void Voice()
    {
        System.Console.WriteLine("???");
    }
    public void Sex()
    {
        if (sex)
        {
            System.Console.WriteLine("female");
        }
        else
        {
            System.Console.WriteLine("male");
        }
    }
}

class Egg : Cicken
{
    public string state;
    public Egg(bool Csex) : base(Csex)
    {
        state = "egg";
    }
    new public void Voice()
    {
        System.Console.WriteLine("korokoro");
    }
}

class Ocs
{
    static void Main()
    {
        Cicken cicken = new Cicken(true);
        Egg egg = new Egg(false);

        cicken.Voice();
        cicken.Sex();
        egg.Voice();
        egg.Sex();
    }
}

実行結果

???
female
korokoro
male

こうすると動いた。
Rubyだと親クラスにinitializeメソッドを書くだけで勝手に初期化してくれるのでC#は少し面倒だ。
まあいちいちコンストラクタを書いたりbase()と明記させることによって人に親クラス子クラスについて考えさせてくれるのかもしれない。

はじめに

XOR

使用例

XOR交換

XOR暗号

Xorshift

最後に

なでしこについて

日本語プログラミング

書き方

変数

四則演算

条件分岐

繰り返し

配列

ハッシュ

おすすめサイト

関連製品

最後に

A問題

B問題

C問題

D問題

まとめ

はじめに

予選A

A問題

B問題

C問題

D問題

まとめ

はじめに

迷い

意識レベルMAX

MacBookユーザの夜の夢

最後に

Ko(int fuga) : base(fuga){ ... }