ビット演算で減算を実装する【アルゴリズム実技検定解説】

第二回アルゴリズム実技検定 (2020年4月) の問題 A - エレベーターのコードをいくつか書きましょう。

atcoder.jp

問題文 (抜粋)

下から順に B9, B8, ..., B1, 1F, 2F, ..., 9F と呼ばれる 18 のフロアを持つ建物があります。
エレベーターが S から T へ移動するには最短で何秒を要するでしょうか。

問題文から、減法演算 (引き算、差) を使って解けそうだと判断できます。
実際の仕事現場であれば減法演算子 - を利用するだけでしょう。

しかし、アルゴリズム実技検定 (PAST) では

1からプログラムを作成する能力を問う

と標榜しているわけですから、
そんな飛び道具に頼った実装は許されないと容易に想像できます。
すなわち、ビット演算 (AND、OR、XOR、NOT、シフト、等値比較) を駆使して
この問題に取り組むのです。

その前にまず、普通に実装したときのソースコードを示しておきましょう。
前回に引き続き、使用言語は C# です。
B1 を -1、1F を 0、2F を 1、・・・と考えれば次のように書けます。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? s[0] - '1' : '0' - s[1]);
        Console.WriteLine(Math.Abs(f[0] - f[1]));
    }
}

上記のコードには、減算が3回のほか、絶対値 Math.Abs が1回含まれています。
これらをビット演算で置き換えます。

前回 (加算) と同様に、再帰を使って減算のコードを書いてみます。
使用言語は C# ですが、他のプログラミング言語でも同様のことができると思います。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? Subtract(s[0], '1') : Subtract('0', s[1]));
        Console.WriteLine(Abs(Subtract(f[0], f[1])));
    }

    static int Subtract(int x, int y)
    {
        var xor = x ^ y;
        var carry = (xor & y) << 1;
        return carry == 0 ? xor : Subtract(xor, carry);
    }

    static int Abs(int x) => (x & 1 << 31) == 0 ? x : ~Subtract(x, 1);
}

carry は繰り下げを表しています。

1 << 31 は int.MinValue と同義であり、コンパイル時に定数として埋め込まれます。
その値は $-2^{31}$ (16進数表記では 80000000) です。

2の補数 (-1倍) については、「1の補数に1を足したもの」の代わりに
「1を引いたものの1の補数」としています。

なお、x - y を x + (-y) と考えれば、
前回 (加算) で作成した Add 関数を用いて Add(x, Add(~y, 1)) としてもよいでしょう。

これで真の AC (正解) が得られました。

また、再帰を使わず、while や for を使って次のようにも書けます。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? Subtract(s[0], '1') : Subtract('0', s[1]));
        Console.WriteLine(Subtract(f[0], f[1]).ToString().Replace("-", ""));
    }

    static int Subtract(int x, int y)
    {
        while (y != 0) y = ((x ^= y) & y) << 1;
        return x;
    }
}