絶対値を求める

Program

高専時代の友人から聞かれた問題がなかなか面白かった。たまにはこういうのもいいね、たまには。

問題1
擬似命令「abs a, b」は、bの絶対値をaに格納するものである。これを、分岐命令を使わずに3命令で実現せよ。ただし、CPUはRISC系、負数は2の補数を使用し、bは32bitの整数とする。
問題2
擬似命令「slt a, b, c」は、b > c*1ならaに1を、b < cならaに0を格納するものである。これを、分岐命令を使わずに3命令*以上*で実現せよ*2。条件は問題1と同じである。

以下解答例

解答例1

  1. b OR 0x40000000を計算
  2. それを30右にビットシフト
  3. それにbをかける

C言語風のコードはこんな感じ。

int myabs(int b) {
    return ((b | 0x40000000) >> 30) * b;
}

まず最初にこの方法を考え付いた。で、これを教えてあげる。

解答例2

  1. bを31ビット右シフトしたものをtに格納
  2. a XOR tを計算
  3. その結果からtを引く

C言語風のコードはこんな感じ。

int myabs(int b) {
    return (b ^ (b >> 31)) - (b >> 31);
}

次に、この方法を考え付いた。ネットで調べるとこれは有名な方法らしい。

解答例3

  1. bを31ビット右にシフト
  2. それと1をOR
  3. それにbをかける

C言語風のコードはこんな感じ。

int myabs(int b) {
    return ((b >> 31) | 1) * b;
}

これは、この問題を聞いてきた友人が解答例1を元に考えたもの。一度に32bitを扱うことが出来ないらしい*3。ちなみに、そのCPUはXORがないので、この解答を提出したそうな。

問題2は、absを参考に、bとcを引き算して最上位ビットを最下位ビットにシフトして、マスクかければOKなので例は出さない。

その後

教授は解答2を例として出したらしい・・・ しかも、「自分で考えた」らしい・・・ 本当なんだろうか・・・
はて、XORは使えなかったのでは*4・・・

*1:符号の向きはあいまい

*2:b == cのときはなんでもいい、ということで

*3:そんな条件聞いてない・・・

*4:自分の性格が歪んでいるだけでしょうけど、とてもその教授が自分で考えたとは思えません