Home > 一般 > 問題

問題

  • 2005-02-23 (Wed) 22:19
  • 一般

「数字 2, 2, 3 と,加減乗除 +, -, *, /, 単項マイナス -, 論理演算 &, |, ^, ~ [and, or, xor, not], シフト <<, >> を用いて 0 ~ 10 の数を作れ.」などという問題を夕飯の調達中に考えていた.

とにかく ALU で実行できる演算と3つの即値で目的の数字を作るという単純明快な目的である.しかしながら,これは結構難しい問題であり,計算機にやらせようとしても計算時間がかかりすぎるので実際に解かせるのは難しい.(簡単なやり方はスタックマシンをシミュレートすることだろうけど...)とはいうものの,夕飯を食べ終わるまで考え続けた結果としてなかなか面白い答えを導くことに成功した.その結果を用いると,たとえば 1,1,1 と上の演算子で任意の数字を作れることになる.

原理の肝は,NOT が1の補数であり,単項マイナスが2の補数であることによる.すなわち, -n = ~n+1 という関係式が成り立つため,+1はいつでも作れる. これにさえ気づけば任意の数字を巣くることが可能であることもすぐに想像がつく.つまり, -~x = x + 1, ~-x = x - 1 を繰り返せばよいのである.

ちなみにこの事実は「ハッカーのたのしみ」の最初のほうに書かれていたりもし,知っている人は知っていることのようである.

★下記に2つの英単語をスペースで区切って入力してください

Home > 一般 > 問題

Search
Feeds

Page Top