ビット演算

http://d.hatena.ne.jp/takeda25/20131018/1382085336

大学4年生の頃、所属の研究室の講師の先生に次のような問題を出されたのを思い出した。

「標準入力から入力されたある程度の長さの文字列を逆順に出力せよ。ただし、ソース上 -（マイナス記号）を使ってはならない」

マイナスが使えないので、配列かなんかに順番に入力を格納していってもそのまま戻りつつ出力するということができないのが焦点ね。

言語は一応Cだったかな。あんまりリッチなライブラリとか使わない前提。自分でも自分なりに回答をだしたんだけど、友人にも解いてもらったらそれぞれ違う回答で面白かった。

友人A

十分な長さのバッファをとっておいて、そこに入力された文字を順に入れていく。入れ終わった最後にはもちろん終端の分かる文字を入れておく。で、出力時には先頭からスキャンしていって最後の文字を探す。見つけたらその一文字を出力して終端の文字でつぶす。そしてまた先頭から同じことを繰り返す。あまりしっかり覚えてないけど、スキャン中に直前の文字を覚えているポインタを用意しておくんだったろうと思う。

当時はこれが順当な回答のような気がした。

友人B

二つ目の解法は、簡単にいうと 加減が使えないなら乗除で代用すれば良いじゃん、という訳で、ものすごい大きなバッファを用意しておいて文字が入力される度n*2の位置に入力文字を入れていく。出力する際には2で割りながら戻ってくる。

まあバッファの大きさがそれでいいのかって感じなんだけど、ロジック自体はシンプルになりますね。

出題者の正解

まあ分かる人は分かるんだろうけど、再起ですね。一文字とりこんで再起呼び出し。戻り時に出力していく。素直にスマートだとおもいました。

私の回答

もったいぶって最後に書く訳だけれども。

マイナスが使えないならマイナスを作り出せば良い、というわけで、座学でよく出てくる2の補数ってやつで、+1をビット反転して1を足すことで-1にして、それを使って戻りのループをまわす、と。これは想定外だったろうと意気揚々と講師の先生に披露したら負数を1の補数で表現する系もあって・・・とか反論されたな。

他にもレギュレーションぎりぎりアウトかもだけど三角関数使うとかあったかな。

で

まあ、ビットをどうこうするってのは、社会人になってからは正直あまりやった覚えが無い・・・ので、ふと思い出したんだと思う。まあ関わってる業種・業界によってはビット演算とかあまりお目にかからないのだなあ。

ま、10年ほど前の大学生の回答なのでいろいろあれかもしれないけど、三者三様なのが面白い。もっといろいろな人に聞いてみれば、まだまだ面白い回答が出てくるかな？