Yet Another Scala Problems (6)

●問題51

演算子 &&, ||, not を用いて排他的論理和を求める関数 xor(p, q) を定義してください。

def xor(p: Boolean, q: Boolean): Boolean

scala> xor(true, true)
val res0: Boolean = false

scala> xor(true, false)
val res1: Boolean = true

scala> xor(false, true)
val res2: Boolean = true

scala> xor(false, false)
val res3: Boolean = false

●問題52

2 つの真偽値 p, q を与えたとき、次に示すような真偽値 s, c を出力する関数 halfAdder(p, q) を定義してください。s, c はタプルで返すものとします。

def halfAdder(p: Boolean, q: Boolean): (Boolean, Boolean)

scala> halfAdder(false, false)
val res0: (Boolean, Boolean) = (false,false)

scala> halfAdder(true, false)
val res1: (Boolean, Boolean) = (true,false)

scala> halfAdder(false, true)
val res2: (Boolean, Boolean) = (true,false)

scala> halfAdder(true, true)
val res3: (Boolean, Boolean) = (false,true)

●問題53

3 つの真偽値 p, q, r を与えたとき、次に示すような真偽値 s, c を出力する関数 fullAdder(p, q, r) を定義してください。s, c はタプルで返すものとします。

def fullAdder(p: Boolean, q: Boolean, r: Boolean): Boolean

scala> fullAdder(false, false, false)
val res0: (Boolean, Boolean) = (false,false)

scala> fullAdder(true, false, false)
val res1: (Boolean, Boolean) = (true,false)

scala> fullAdder(true, true, false)
val res2: (Boolean, Boolean) = (false,true)

scala> fullAdder(true, true, true)
val res3: (Boolean, Boolean) = (true,true)

●問題54

true, false とリストで n ビットの無符号整数を表すことにします。これを uint と呼ぶことにしましょう。たとえば、0 と 255 を 8 桁の unit で表すと次のようになります。

       MSB                                               LSB
  0 : (false, false, false, false, false, false, false, false)
255 : (true,  true,  true,  true,  true,  true,  true,  true)

0 以上の整数値 n を m 桁の uint に変換する関数 int2uint(n, m) と、uint を整数値に変換する関数 uint2int(xs) を定義してください。

type uint = List[Boolean]
def int2uint(n: Int, m: Int): uint
def uint2int(xs: uint): Int

scala> int2uint(0, 8)
val res0: yasp06.uint = List(false, false, false, false, false, false, false, false)

scala> int2uint(127, 8)
val res1: yasp06.uint = List(false, true, true, true, true, true, true, true)

scala> int2uint(128, 8)
val res2: yasp06.uint = List(true, false, false, false, false, false, false, false)

scala> int2uint(255, 8)
val res3: yasp06.uint = List(true, true, true, true, true, true, true, true)

scala> uint2int(List(true, true, true, true))
val res4: Int = 15

scala> uint2int(List(false, false, false, false))
val res5: Int = 0

scala> uint2int(List(false, false, false, true))
val res6: Int = 1

scala> uint2int(List(true, false, false, false))
val res7: Int = 8

●問題55

uint で論理演算を行う関数 uintAnd, uintOr, uintXor, uintNot を定義してください。

def uintAnd(xs: uint, ys: uint): uint
def uintOr(xs: uint, ys: uint): uint
def uintXor(xs: uint, ys: uint): uint
def uintNot(xs: uint): uint

scala> val a = List(false, false, true, true)
val a: List[Boolean] = List(false, false, true, true)

scala> val b = List(false, true, false, true)
val b: List[Boolean] = List(false, true, false, true)

scala> uintAnd(a, b)
val res0: yasp06.uint = List(false, false, false, true)

scala> uintOr(a, b)
val res1: yasp06.uint = List(false, true, true, true)

scala> uintXor(a, b)
val res2: yasp06.uint = List(false, true, true, false)

scala> uintNot(a)
val res3: yasp06.uint = List(true, true, false, false)

●問題56

2 つの uint を加算する関数 uintAdd(xs, ys) を定義してください。uintAdd はタプルを返します。桁あふれが生じた場合、2 番目の返り値は true になります。なお、xs, ys の桁は同じものとします。

def uintAdd(xs: uint, ys: uint): (uint, Boolean)

scala> uintAdd(List(false, true, true), List(false, false, true))
val res0: (yasp06.uint, Boolean) = (List(true, false, false),false)

scala> uintAdd(List(true, true, true), List(false, false, true))
val res1: (yasp06.uint, Boolean) = (List(false, false, false),true)

●問題57

uint を +1 する関数 uintInc(xs) を定義してください。uintInc はタプルを返します。桁あふれが生じた場合、2 番目の返り値は true になります。

def uintInc(xs: uint): uint

scala> uintInc(List(false, false, false))
val res0: (yasp06.uint, Boolean) = (List(false, false, true),false)

scala> uintInc(List(true, true, true))
val res1: (yasp06.uint, Boolean) = (List(false, false, false),true)

●問題58

2 つの uint を減算する関数 uintSub(xs, ys) を定義してください。uintSub はタプルを返します。桁借りが生じた場合、2 番目の返り値は true になります。なお、xs, ys の桁は同じものとします。

def uintSub(xs: uint, ys: uint): (uint, Boolean)

scala> uintSub(List(true, true, true, false), List(false, true, false, true))
val res0: (yasp06.uint, Boolean) = (List(true, false, false, true),false)

scala> uintSub(List(true, true, true, false), List(true, true, true, true))
val res1: (yasp06.uint, Boolean) = (List(true, true, true, true),true)

scala> uintSub(List(true, true, true, true), List(true, true, true, true))
val res2: (yasp06.uint, Boolean) = (List(false, false, false, false),false)

●問題59

uint を左へ 1 ビット論理シフトする関数 uintSll と、右へ 1 ビット論理シフトする関数 uintSrl を定義してください。uintSll と uintSrl はタプルを返します。2 番目の返り値は uintSll であれば MSB、uintSrl であれば LSB になります。

def uintSrl(xs: uint): (uint, Boolean)
def uintSll(xs: uint): (uint, Boolean)

scala> uintSrl(List(true, false, true, false))
val res0: (yasp06.uint, Boolean) = (List(false, true, false, true),false)

scala> uintSrl(List(false, true, false, true))
val res1: (yasp06.uint, Boolean) = (List(false, false, true, false),true)

scala> uintSll(List(true, false, true, false))
val res2: (yasp06.uint, Boolean) = (List(false, true, false, false),true)

scala> uintSll(List(false, true, false, true))
val res3: (yasp06.uint, Boolean) = (List(true, false, true, false),false)

●問題60

次に示す uint の比較関数を定義してください。なお、引数 xs, ys の桁は同じものとします。

scala> val a = List(true, false, false, false)
a: List[Boolean] = List(true, false, false, false)

scala> val b = List(false, true, true, true)
b: List[Boolean] = List(false, true, true, true)

scala> uintEqual(a, b)
val res0: Boolean = false

scala> uintEqual(a, a)
val res1: Boolean = true

scala> uintZero(List(false, false, false, false))
val res2: Boolean = true

scala> uintZero(List(false, false, false, true))
val res3: Boolean = false

scala> uintGreater(a, b)
val res4: Boolean = true

scala> uintGreater(b, a)
val res5: Boolean = false

scala> uintLess(a, b)
val res6: Boolean = false

scala> uintLess(b, a)
val res7: Boolean = true

●問題61

2 つの uint を乗算する関数 uintMul(xs, ys) を定義してください。桁あふれは無視してください。なお、xs, ys の桁は同じものとします。

def uintMul(xs: uint, ys: uint): uint

scala> uintMul(List(false, false, true, true), List(false, false, false, false))
val res0: yasp06.uint = List(false, false, false, false)

scala> uintMul(List(false, false, true, true), List(false, false, false, true))
val res1: yasp06.uint = List(false, false, true, true)

scala> uintMul(List(false, false, true, true), List(false, false, true, false))
val res2: yasp06.uint = List(false, true, true, false)

scala> uintMul(List(false, false, true, true), List(false, false, true, true))
val res3: yasp06.uint = List(true, false, false, true)

●問題62

2 つの uint を除算する関数 uintDiv(xs, ys) を定義してください。uintDiv は商と余りをタプルで返します。なお、xs, ys の桁は同じものとします。

def uintDiv(xs: uint, ys: uint): (uint, uint)

scala> uintDiv(List(true, true, true, true), List(false, false, true, false))
val res0: (yasp06.uint, yasp06.uint) = (List(false, true, true, true),List(false, false, false, true))

scala> uintDiv(List(true, true, true, true), List(false, true, false, false))
val res1: (yasp06.uint, yasp06.uint) = (List(false, false, true, true),List(false, false, true, true))

scala> uintDiv(List(true, true, true, true), List(true, false, false, false))
val res2: (yasp06.uint, yasp06.uint) = (List(false, false, false, true),List(false, true, true, true))

●解答51

真偽値 p, q の論理演算は全部で 16 通りあります。これらの論理演算は not, and, or の組み合わせで実現することができます。

    否定
 p     not
-------------
 false true
 true  false

              論理積  論理和  否定論理積  否定論理和  排他的論理和
 p     q       and      or       nand        nor          xor
-------------------------------------------------------------------
 false false  false   false      true       true         false
 false true   false   true       true       false        true
 true  false  false   true       true       false        true
 true  true   true    true       false      false        false

演算結果が true となる所に注目します。排他的論理和の場合、p = false, q = true または p = true, q = false のときに結果は true になります。最初の条件は !p && q で、2 番目の条件は p && !q で表すことができます。あとは 2 つの条件式を演算子 || で結合すればいいわけです。プログラムは次のようになります。

リスト : 排他的論理和

  def xor(p: Boolean, q: Boolean): Boolean = (!p && q) || (p && !q)

  // 別解
  def xor1(p: Boolean, q: Boolean): Boolean = (p || q) && (!(p && q))

別解はブール代数の定理を用いて求めることができます。上図の or と nand の and を計算すると、確かに xor になることがわかります。

●解答52

真理値表から s = p XOR q, c = p AND q であることがすぐにわかります。

リスト : 半加算器

  def halfAdder(p: Boolean, q: Boolean): (Boolean, Boolean) = (xor(p, q), p && q)

これを論理回路で実現すると「半加算器」になります。s は 1 ビットの加算、c が桁上がりを表します。ただし、半加算器は入力が 2 つしかないので、下位の桁上がりを受け取ることができません。整数の加算回路を実現するには、次に示す全加算器を使います。

●解答53

r を桁上がりと考えると、真理値表は 1 ビットの加算を表していることがわかります。この真理値表を出力する論理回路を「全加算器」といいます。全加算器は 2 つの半加算器と or を使って実現することができます。

リスト : 全加算器

  def fullAdder(p: Boolean, q: Boolean, r: Boolean): (Boolean, Boolean) = {
    val (a, b) = halfAdder(p, q)
    val (c, d) = halfAdder(a, r)
    (c, b || d)
  }

最初に p と q を halfAdder で加算します。値は a, b にセットします。次に、a と r を halfAdder で加算します。値は c と d にセットします。加算の結果は c になり、桁上がりは b || d で求めることができます。

●解答54

リスト : 数値を m 桁の uint に変換

  type uint = List[Boolean]

  def isOdd(n: Int): Boolean  = n % 2 != 0
  def isEven(n: Int): Boolean = n % 2 == 0

  def int2uint(n: Int, m: Int): uint = {
    def iter(n: Int, a: uint): uint =
      if (a.length == m) a else iter(n / 2, isOdd(n)::a)
    //
    iter(n, Nil)
  }

int2uint は簡単です。ビットオンを true に、ビットオフを false に変換するだけです。数値 n が奇数の場合、LSB は 1 なので累積変数 a に true を追加します。そうでなければ false を追加します。この処理は述語 isOdd を使うと簡単です。あとは n を 2 で割り算し、ビットを順番に調べていくだけです。

リスト : uint を数値に変換

  def uint2int(xs: uint): Int =
    xs.foldLeft(0)((a: Int, x: Boolean) => if (x) a * 2 + 1 else a * 2)

uint2int も簡単です。foldLeft で要素を順番に取り出し、要素 n が true ならば累積変数 a を 2 倍して 1 を足し算します。false ならば 1 を足し算しません。

●解答55

リスト : 論理演算

  // 論理積
  def uintAnd(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => z._1 && z._2)

  // 論理和
  def uintOr(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => z._1 || z._2)

  // 排他的論理和
  def uintXor(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => xor(z._1, z._2))

  // 否定
  def uintNot(xs: uint): uint = xs.map(!_)

論理演算は zip と map を使うと簡単です。map の匿名関数の引数 z (タプル) の第 1 要素と第 2 要素を &&, ||, xor で処理するだけです。否定はリストの要素に演算子 ! を適用するだけです。

●解答56

リスト : 加算

  def uintAdd(xs: uint, ys: uint): (uint, Boolean) =
    xs.zip(ys).foldRight((Nil: uint, false))(
      (z, a) => {
        val (s, c) = fullAdder(z._1, z._2, a._2)
        (s::a._1, c)
      }
    )

uintAdd は zip, foldRight, fullAdder を使うと簡単です。foldRight でリスト xs, ys の最後尾の要素から fullAdder を順番に適用して加算処理を行います。匿名関数の引数 z がリスト x とリスト y の要素を格納したタプル、第 2 引数 a のタプルが累積変数です。タプルの先頭要素 a._1 が uint を表すリスト、a._2 が桁上がりの有無を表す真偽値です。初期値は空リストと false に設定します。あとは fullAdder の返り値 (s, c) の s を a._1 の先頭に追加し、それと c をタプルに格納して返すだけです。

●解答57

リスト : uint をインクリメントする

  def uintInc(xs: uint): (uint, Boolean) =
    xs.foldRight((Nil: uint, true))(
      (x, a) => {
        val (s, c) = halfAdder(x, a._2)
        (s::a._1, c)
      }
    )

uintInc は uintAdd とほとんど同じです。foldRight に渡す初期値を空リストと true に設定します。これで引数 xs を +1 することができます。

●解答58

減算は 2 の補数を使って計算します。簡単な例として 4 ビットの整数値を考えてみましょう。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。

 0 : 0000
 1 : 0001    -1 : 1111
 2 : 0010    -2 : 1110
 3 : 0011    -3 : 1101
 4 : 0100    -4 : 1100
 5 : 0101    -5 : 1011
 6 : 0110    -6 : 1010
 7 : 0111    -7 : 1001
             -8 : 1000

    図 : 2 の補数

2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。たとえば 7 - 2 は 7 + (-2) = 0111 + 1110 = 1 0101 となり、桁上がりを無視すると値は 5 になります。また、15 - 14 は (-1) - (-2) = (-1) + 2 = 1111 + 0010 = 1 0001 となり、正しく計算することができます。

逆に、2 - 7 は 2 + (-7) = 0010 + 1001 = 1011 になります。この場合、2 の補数で考えると 1011 は -5 になるので、符号付き整数では正しい値になりますが、無符号整数で考えると桁借りが発生しています。したがって、減算したときの桁借りの有無は、加算したときの桁上がりの値を反転することで求めることができます。

プログラムは次のようになります。

リスト : 減算

  def uintSub(xs: uint, ys: uint): (uint, Boolean) = {
    val (a, _) = uintInc(uintNot(ys))
    val (s, c) = uintAdd(xs, a)
    (s, !c)
  }

uintNot(ys) で 1 の補数を求め、uintInc で +1 することで 2 の補数を求めることができます。あとは uintAdd で xs と加算するだけです。値を返すとき、演算子 ! で c の値を反転することをお忘れなく。

●解答59

リスト : 論理シフト

  def uintSrl(xs: uint): (uint, Boolean) = (false::xs.init, xs.last)

  def uintSll(xs: uint): (uint, Boolean) = (xs.tail ::: List(false), xs.head)

論理シフトも簡単です。uintSrl はメソッド init で最後尾のセルを取り除き、先頭に false を追加します。メソッド last は最後尾の要素を取り出します。uintSll は tail で先頭要素を取り除き、演算子 ::: で最後尾に List(false) を追加するだけです。

●解答60

リスト : uint の比較関数

  def uintEqual(xs: uint, ys: uint): Boolean = xs == ys
  def uintZero(xs: uint): Boolean = xs.forall(!_)

  def uintGreater(xs: uint, ys: uint): Boolean =
    (xs, ys) match {
      case (Nil, Nil) => false
      case (x::xs1, y::ys1) => if (x == y) uintGreater(xs1, ys1) else x
      case _ => throw new Exception("uintGreater: Empty List")
    }

  def uintLess(xs: uint, ys: uint): Boolean =
    (xs, ys) match {
      case (Nil, Nil) => false
      case (x::xs1, y::ys1) => if (x == y) uintLess(xs1, ys1) else y
      case _ => throw new Exception("unitLess: Empty List")
    }

uintEequal は比較演算子 == で xs と ys を比較するだけです。unitZero はメソッド forall ですべての要素が false であることを確認します。uintGreater は xs と ys の要素を先頭から順番に比較し、xs の要素と ys の要素が等しい場合は uintGreater を再帰呼び出しします。要素が異なる場合、要素 x が true ならば x が大きいので true を返します。そうでなければ false を返します。つまり、x の値を返せば良いわけです。uintLess も同様にプログラムできます。

●解答61

筆算のアルゴリズムをそのまま 2 進数に適用します。たとえば、1 1 0 1 と 1 0 1 の乗算は次のように計算します。

       1 1 0 1
 *       1 0 1
 --------------
       1 1 0 1
     0 0 0 0
   1 1 0 1
 -------------
 1 0 0 0 0 0 1


図 : 1101 * 101

このアルゴリズムはビットシフトと加算で実現することができます。桁あふれのチェックは行わないことにすると、プログラムは次のようになります。

リスト : uint の 乗算

  def makeZero(n: Int): uint = List.fill(n)(false)

  def uintMul(xs: uint, ys: uint): uint = {
    val (zs, _) = ys.foldRight((makeZero(xs.length), xs))(
      (y, a) => {
        val (c, _) = uintSll(a._2)
        if (y) (uintAdd(a._1, a._2)._1, c) else (a._1, c)
      }
    )
    zs
  }

foldRight で ys の LSB から計算を始めます。匿名関数の引数 y が ys の要素、第 2 引数 a にはタプルを渡します。第 1 要素が累積値、第 2 要素が累積値に加算する値です。最初は 0 と x に初期化します。y が真のときは a._1 に a._2 を加算します。そうでなければ、a._2 を加算しません。この値と uintSll で a._1 を 1 ビット左シフトした値をタプルに格納して返します。最後に foldRight の返り値から累積値を取り出して返します。

●解答62

筆算のアルゴリズムをそのまま 2 進数に適用します。次の図を見てください。

     1 0 1 0 1
---------------
 1 1 0 1 0 1 1
 1 0 1 0 0 0 0
---------------
     1 1 0 1 1
     1 0 1 0 0
   ------------
         1 1 1
         1 0 1
         ------
           1 0

図 : 1101011 / 101

xs (1101011) を ys (101) で除算する場合、最初に ys を左シフトして桁合わせを行います。上図の場合、1101011 から ys を 4 ビットシフトした値 zs (1010000) を引き算して余り q が 11011 になります。このとき、商 p に 1 をセットします。次に、zs を右へ 1 ビットシフトした 101000 と q を比較します。この場合、q のほうが小さいので引き算できません。p の値は左へ 1 ビットシフトして 10 になります。

あとは同様に、zs を右へ 1 ビットシフトして q と比較します。引き算できる場合は p を左へ 1 ビットシフトしてから値を +1 します。引き算できない場合は p を左へ 1 ビットシフトするだけです。上図の場合、10100 は 11011 よりも小さいので、p の値は 101 になり、q の値は 111 になります。次に、1010 は 111 よりも大きいので p の値は 1010 になります。最後に、101 は 111 よりも小さいので、p の値は 10101 になり、q の値は 10 になります。これで商 p と余り q を求めることができます。

プログラムは再帰定義を使うと簡単です。次のリストを見てください。

リスト : uint の除算

  def uintDiv(xs: uint, ys: uint): (uint, uint) =
    if (uintLess(xs, ys)) (makeZero(xs.length), xs)
    else if (uintEqual(xs, ys) || (ys.head))
      (uintInc(makeZero(xs.length))._1, uintSub(xs, ys)._1)
    else {
      val (p, q) = uintDiv(xs, uintSll(ys)._1)
      if (uintLess(q, ys)) (uintSll(p)._1, q)
      else (uintInc(uintSll(p)._1)._1, uintSub(q, ys)._1)
    }

uintDiv は再帰呼び出しするたびに引数 ys を 1 ビット左シフトして桁合わせを行います。xs が ys よりも小さい場合は除算できないので商 0 と余り xs をタプルで返します。xs と ys が等しい、または y の MSB が true の場合、商は 1 で余りが xs - ys になります。

これ以外の場合、ys を 1 ビット左シフトして uintDiv を再帰呼び出しします。余り q が ys よりも小さい場合、p を 1 ビット左シフトした値と q を返します。そうでなければ、p を 1 ビット左シフトしてから +1 した値と q - ys を返します。これで商と余りを求めることができます。

●プログラムリスト

//
// yasp06.scala : Yet Another Scala Problems (6)
//
//                Copyright (C) 2014-2024 Makoto Hiroi
//

object yasp06 {
  // Q61
  def xor(p: Boolean, q: Boolean): Boolean = (!p && q) || (p && !q)

  // 別解
  def xor1(p: Boolean, q: Boolean): Boolean = (p || q) && (!(p && q))

  // Q62
  def halfAdder(p: Boolean, q: Boolean): (Boolean, Boolean) = (xor(p, q), p && q)

  // Q63
  def fullAdder(p: Boolean, q: Boolean, r: Boolean): (Boolean, Boolean) = {
    val (a, b) = halfAdder(p, q)
    val (c, d) = halfAdder(a, r)
    (c, b || d)
  }

  // Q64
  type uint = List[Boolean]

  def isOdd(n: Int): Boolean  = n % 2 != 0
  def isEven(n: Int): Boolean = n % 2 == 0

  // Int -> uint
  def int2uint(n: Int, m: Int): uint = {
    def iter(n: Int, a: uint): uint =
      if (a.length == m) a else iter(n / 2, isOdd(n)::a)
    //
    iter(n, Nil)
  }

  // uint -> Int
  def uint2int(xs: uint): Int =
    xs.foldLeft(0)((a: Int, x: Boolean) => if (x) a * 2 + 1 else a * 2)

  // Q55
  // 論理積
  def uintAnd(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => z._1 && z._2)

  // 論理和
  def uintOr(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => z._1 || z._2)

  // 排他的論理和
  def uintXor(xs: uint, ys: uint): uint =
    xs.zip(ys).map(z => xor(z._1, z._2))

  // 否定
  def uintNot(xs: uint): uint = xs.map(!_)

  // Q56
  def uintAdd(xs: uint, ys: uint): (uint, Boolean) =
    xs.zip(ys).foldRight((Nil: uint, false))(
      (z, a) => {
        val (s, c) = fullAdder(z._1, z._2, a._2)
        (s::a._1, c)
      }
    )

  // Q57
  def uintInc(xs: uint): (uint, Boolean) =
    xs.foldRight((Nil: uint, true))(
      (x, a) => {
        val (s, c) = halfAdder(x, a._2)
        (s::a._1, c)
      }
    )

  // Q58
  def uintSub(xs: uint, ys: uint): (uint, Boolean) = {
    val (a, _) = uintInc(uintNot(ys))
    val (s, c) = uintAdd(xs, a)
    (s, !c)
  }

  // Q59
  def uintSrl(xs: uint): (uint, Boolean) = (false::xs.init, xs.last)
  def uintSll(xs: uint): (uint, Boolean) = (xs.tail ::: List(false), xs.head)

  // Q60
  def uintEqual(xs: uint, ys: uint): Boolean = xs == ys
  def uintZero(xs: uint): Boolean = xs.forall(!_)

  def uintGreater(xs: uint, ys: uint): Boolean =
    (xs, ys) match {
      case (Nil, Nil) => false
      case (x::xs1, y::ys1) => if (x == y) uintGreater(xs1, ys1) else x
      case _ => throw new Exception("uintGreater: Empty List")
    }

  def uintLess(xs: uint, ys: uint): Boolean =
    (xs, ys) match {
      case (Nil, Nil) => false
      case (x::xs1, y::ys1) => if (x == y) uintLess(xs1, ys1) else y
      case _ => throw new Exception("unitLess: Empty List")
    }

  // Q61
  def makeZero(n: Int): uint = List.fill(n)(false)

  def uintMul(xs: uint, ys: uint): uint = {
    val (zs, _) = ys.foldRight((makeZero(xs.length), xs))(
      (y, a) => {
        val (c, _) = uintSll(a._2)
        if (y) (uintAdd(a._1, a._2)._1, c) else (a._1, c)
      }
    )
    zs
  }

  // Q62
  def uintDiv(xs: uint, ys: uint): (uint, uint) =
    if (uintLess(xs, ys)) (makeZero(xs.length), xs)
    else if (uintEqual(xs, ys) || (ys.head))
      (uintInc(makeZero(xs.length))._1, uintSub(xs, ys)._1)
    else {
      val (p, q) = uintDiv(xs, uintSll(ys)._1)
      if (uintLess(q, ys)) (uintSll(p)._1, q)
      else (uintInc(uintSll(p)._1)._1, uintSub(q, ys)._1)
    }
}