Scala进阶笔记---32位加法实现

昨晚一位朋友去面试某一知名互联网公司，对方出了一道题，问如何实现32位加法？

我第一时间反应，将两个加数分别转换成十进制，再调用十进制的“+” 进行操作，结果再转换回32进制即可。

朋友告诉我，对方不许转10进制。

我说，那转2进制吧，1位扩展成5位，累加更方便。结果长度不被5整除，头部就补0，也好做。

对方说，也不能转2进制。

那你明说嘛，就是想要模拟我们小学的加号算法，运用到32进制上，是不？

对，就是这个意思！

OK，talk is cheap, show me the code：

import java.io.IOException

import scala.collection.mutable

/**
  * Created by nicky_ye on 2018/2/8.
  */
object hex_32_add {
  val char_list = List('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
    'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'R', 'S', 'T', 'U', 'W', 'X', 'Y', 'Z')
  val char_list_map: mutable.Map[Char, Int] = mutable.Map()
  for (i <- char_list) {
    char_list_map += (i -> char_list.indexOf(i))
  }

  def hex_32_add(string1: String, string2: String): String = {
    if (!string1.forall(x => char_list.contains(x)) || !string2.forall(y => char_list.contains(y))) {
      throw new IOException("Wrong Input String")  ////pre check of input strings' legality
    }
    else {
      var string1_reverse: Array[Char] = string1.reverse.toArray
      var string2_reverse: Array[Char] = string2.reverse.toArray
      var result_list: Array[Char] = Array()
      var add_next_column = 0 //sign进位标志符
      for (i <- 0 until math.max(string1_reverse.length, string2_reverse.length)) {
        if (i >= string1_reverse.length) string1_reverse = string1_reverse.:+('0')
        if (i >= string2_reverse.length) string2_reverse = string2_reverse.:+('0')

        var column_result = char_list_map(string1_reverse(i)) + char_list_map(string2_reverse(i)) + add_next_column
        if (column_result > 31) {
          add_next_column = 1
          column_result -= 32
        }
        else {
          add_next_column = 0
        }
        result_list = result_list.:+(char_list(column_result))
      }
      if (add_next_column == 1) result_list = result_list.:+('1')
      result_list.toList.toString.replace("List(","").replace(", ","").replace(")","").reverse
    }
  }
}

基本思想：
1：以两个String为输入，以一个String为输出，String代表32进制字符
2：0到9，A到Z，分别代表0~31，String中除此之外的字符不合法
3：add_next_column表示进位标识符，初始化0
4：输入字符串 ---> 翻转reverse---> 转数组Array[Char]
5：若两个输入String长度不相等，则短的翻转后补0对齐
6：逐位相加再加进位符，若结果超过32，进位标识符记1
7：所有位数对齐相加完毕后，若最后一位(即翻转前的最高位)相加结果大于32，即进位标识符又为1，则结果列表中最后再加一位1
8：结果列表result_list转换成String，再翻转reverse，即得最终结果

思路或者代码中，从时间成本/内存成本来考虑，应该有可以优化之处，几个reverse操作，开销感觉也不算小，但是应该也不算大。
我不是专门做这类优化的，有了解的朋友欢迎指点。