yukicoder No.353 ヘイトプラス：プラス記号なしで足し算を行う複数の方法

昨夜、yukicoderにて開催されたyukicoder April Contestに私は参加しました。この記事では、コンテスト中に私が解けた問題の一つである、No.353 ヘイトプラス - yukicoderという問題について、備忘録を兼ねていくつかの解き方を示します。なお、この中には私が自ら思いついたものだけではなく、コンテスト後に調べて知ったものもあります。また、これら以外の解き方も存在するかもしれません。

問題の趣旨

非負整数 ()が与えられるので、を出力せよ。ただし、ソースコードに+を含めてはならない。

解き方と解答例

どうにかして+を使わずに加算を行う必要があります。たとえば以下のような方法が考えられます。ただし、言語によってはとりにくい方法があるかもしれません。

被演算子を要素に持つ配列／リストの総和を求める方法

を配列やリストに入れ、その総和を求めれば、を求めたことになります。これは私がコンテスト中に思いついた方法です。配列／リストの総和を求める関数の例としては、C++のstd::accumulate*1、HaskellやPythonなどのsumが挙げられます。

C++のstd::accumulateを用いた例を以下に示します。

#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>


template <typename T> T add(T a, T b) {
    std::vector<T> v = {a, b};
    return std::accumulate(v.begin(), v.end(), 0);
}


int main(){
    int a, b;
    std::cin >> a >> b;
    std::cout << add(a, b) << std::endl;
    return EXIT_SUCCESS;
}

コンテスト中に私が提出したHaskellコードを以下に示します。大まかには、標準入力からgetLineで1行読み取り、空白区切りの文字列をwordsで文字列のリストにし、map readでそれぞれの文字列を整数にし、sumで総和を求め、printで出力しています。

main :: IO ()
main = print . sum . map read . words =<< getLine

引き算を用いる方法

を利用するという方法もあります。この方法にはコンテスト後の生放送を通じて気づきました。これはさまざまな言語で使えるであろう方法です。次に示すのはC#による解答例です。

using System;
using System.Linq;

namespace yukicoder
{
    class yukicoder0353
    {
        static int Add(int a, int b)
        {
            return a - (-b);
        }

        static void Main(string[] args)
        {
            var xs = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            Console.WriteLine(Add(xs[0], xs[1]));
        }
    }
}

また、次のコードはSchemeによる解答例です。

#!/usr/bin/env gosh
(let* ((a (read)) (b (read)))
  (print (- a (- b))))

関数形式の演算子を用いる方法

言語によっては、+のような基本的な演算子と同じ働きをする関数を標準で利用できます。この方法にはコンテスト後に気づきました。以下に、Pythonのoperator.addを使ったコードを示します。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import operator


def main():
    print(operator.add(*map(int, input().split())))


if __name__ == '__main__':
    main()

ビット演算による方法：全加算器

以下に示すGoコードのように、ビット演算を用いて足し算を実現することもできます。これは足し算を使わずに足し算する — KaoriYaを参考にしたものです。同記事にあるように、これは全加算器（cf. wikipedia:加算器）と呼ばれる論理回路をコードに直したものです。

package main

import "fmt"

func main() {
    // Based on http://www.kaoriya.net/blog/2013/02/04/
	var a, b, c int
	fmt.Scan(&a, &b)
	for b != 0 {
		c = (a & b) << 1
		a ^= b
		b = c
	}
	fmt.Println(a)
}

ポインタを用いた方法

主婦でも出来る!? 算術演算子を使わない算術演算 - Folioscopeで詳しく書かれているように、ポインタや配列参照演算子[]を駆使して整数の足し算を行うこともできます。

感想

この問題を通じて、全加算器というものの存在を知りました。私は今まで論理回路にほとんど触れないままプログラミングをやってきましたが、こういった基礎的事項に目を向ける必要を感じました。

また、この問題のように、特定の機能・関数の使用に制限を課す問題*2はなかなか面白いと思いました。こういった問題は、言語機能や標準ライブラリをよく知るきっかけになりそうです。

*1:むしろHaskellにおけるfoldlのような畳み込みの関数と呼ぶべきかもしれません。

*2:なお、私がこの問題を見たときに、HackerRankのPythonist 3というPython愛好者のための(?)コンテストで出題されたginortSという問題を連想しました。この問題ではfor, join, sortedおよびwhileの使用回数が制限されました。