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

第一回アルゴリズム実技検定 (2019年12月) の問題 A - 2 倍チェックのコードをいくつか書きましょう。

atcoder.jp

問題文 (抜粋)

S が 3 桁の整数である場合 (0 で始まる場合を含む) はその 2 倍の値を出力し、
そうでなければ error と出力するプログラムを作成せよ。

2 倍の値を求める部分については、普通に考えれば 2 * n あるいは n + n のような
四則演算のコードを書くだけにも見えます。

しかし、アルゴリズム実技検定 (PAST) のキャッチフレーズは

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

です。
したがって、そんな単純な実装で許されるはずはなく、
出題者の想定解法は「ビット演算を使って四則演算を実装する」です (断言)。
すなわち、AND、OR、XOR、NOT、シフト、等値比較を駆使してこの問題を解くのです。

というわけで以下では、ビット演算で加法演算 (足し算、和) を自作し、
n + n と同等のコードを実現していきます。
使用言語は C# ですが、他のプログラミング言語でも同様のことができると思います。

using System;

class A
{
    static void Main()
    {
        int n;
        Console.WriteLine(int.TryParse(Console.ReadLine(), out n) ? $"{Add(n, n)}" : "error");
    }

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

上記のように、再帰でシンプルに書けます。 carry は繰り上げを表しています。
これで真の AC (正解) が得られました。

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

using System.Linq;
using static System.Console;

class A
{
    static void Main() => Solve(ReadLine());
    static void Solve(string s) => WriteLine(s.All(char.IsNumber) ? $"{Twice(int.Parse(s))}" : "error");
    static int Twice(int x) => Add(x, x);

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

ちなみに、この問題の場合は 2 倍するだけなので、
実は左シフト演算 n << 1 で達成できます。

using System;

class A
{
    static void Main()
    {
        int n;
        Console.WriteLine(int.TryParse(Console.ReadLine(), out n) ? $"{n << 1}" : "error");
    }
}

次回: ビット演算で減算を実装する