BinaryDivisionRecursion

import java.util.*
import kotlin.math.pow

/**
 * @author Preyea R. Regmi
 * Entry point to the division operation
 * 1) Takes input from CLI as string and parse into decimal format.
 * 2) Converts the input and divisor into binary string
 * 3) Performs division on binary representation
 * 4) Prints Quotient and Remainder in both binary and decimal format
 */
fun main() {

    while(true) {
        val console = Scanner(System.`in`)
        println("Enter dividend number")
        val dividend = console.nextInt()
        println("Enter divisor number")

        val divisor = console.nextInt()

        val inputBinaryString: String = toBinaryString(dividend)
        val divisorBinaryString: String = toBinaryString(divisor)

        println("Dividend Binary: $inputBinaryString")
        println("Divisor Binary: $divisorBinaryString")
        val divResult = divideBinary(inputBinaryString, divisorBinaryString)

        println("Quotient Binary: " + divResult.first)
        println("Remainder Binary: " + divResult.second)
        println("Quotient Decimal: " + divResult.first.toDecimal())
        println("Remainder Decimal: " + divResult.second.toDecimal())
        println()
    }

}

/**
 * Recursive division function for binary representation
 * @param x Input binary string
 * @param y Divisor binary string
 * @return Quotient and Remainder as a Pair
 */
fun divideBinary(x:String, y:String):Pair<String,String>
{
    if(x.isZero())
        return Pair(Integer.toBinaryString(0), Integer.toBinaryString(0));
    val quotientRemainderPair= divideBinary(x.divideBy2(),y)
    var qPrime= quotientRemainderPair.first.multiplyBy2()
    var rPrime = quotientRemainderPair.second.multiplyBy2()
    if(x.isOdd())
        rPrime=rPrime.addWith("1")
    if(rPrime.greaterOrEqualTo(y)) {
        rPrime = rPrime.subtractWith(y)
        qPrime = qPrime.addWith("1")
    }
    return Pair(qPrime,rPrime)

}

/**
 * Extension function on String type compare with another binary string.
 */
fun String.greaterOrEqualTo(x:String):Boolean
{
    val b1=Integer.parseInt(this)
    val b2=Integer.parseInt(x)
    return b1-b2>=0
}

/**
 * Extension function on String type that perfrom division by 2 for binary String.
 * Division by 2 is essentially a logical right shift operation for binary numbers.
 * Since the binary representation is expressed as String which is array of characters,
 * right shifting is just removing the last character in the array.
 */
fun String.divideBy2():String
{
    if(this.length<=1)
        return "0";
    else
        return this.substring(0,this.length-1)
}

/**
 * Division by 2 is essentially a logical left shift operation for binary numbers
 * Since the binary representation is expressed as String which is array of characters,
 * left shifting is just appending '0' in the array.
 */
fun  String.multiplyBy2():String{
    return this+"0";
}

/**
 * Extension function on String type to perform binary addition.
 * Since it was allowed to use std library for add operation.
 */
fun String.addWith(input:String):String
{
    val b1=Integer.parseInt(this,2)
    val b2=Integer.parseInt(input,2)
    return Integer.toBinaryString(b1+b2)
}

/**
 * Extension function on String type to perform binary subtraction
 * Since it was allowed to use std library for subtract operation.
 */
fun String.subtractWith(input:String):String
{
    val b1=Integer.parseInt(this,2)
    val b2=Integer.parseInt(input,2)
    return Integer.toBinaryString(b1-b2)
}

/**
 * Extension function on String type to check if binary string is zero or not
 * If all the character in bit string is zero, it has zero value in decimal form.
 */
fun String.isZero():Boolean
{
    for(bit in this)
    {
        if(bit!='0')
            return false
    }
    return true
}

/**
 * Extension function on String type to check if binary string is odd or not
 * If the last bit of binary string is '1' then it is odd o
 */
fun String.isOdd():Boolean
{
    return (this[this.length-1]=='1')
}

/**
 * Extension function on String type to check if binary string is even or not
 * If the last bit of binary string is '0' then it is even
 */
fun String.isEven():Boolean
{
    return !this.isOdd()
}

/**
 * Recursive function to convert int to binary string.
 */
fun toBinaryString(num: Int): String {
    return if (num == 0) "" else toBinaryString(num / 2 ) + num % 2
}

/**
 * Extension function on String type to convert binary string to decimal.
 */
fun String.toDecimal():Int
{
    var convertedDouble:Double=0.0
    for (i in 0 until this.length) {
        if (this[i] == '1') {
            val len: Int = this.length - 1 - i
            convertedDouble += 2.0.pow(len.toDouble())
        }
    }

    return convertedDouble.toInt()
}