#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

#define SHIFT_RIGHT_ARITHMETIC 1
#define SHIFT_RIGHT_LOGICAL 2
#define SHIFT_LEFT_LOGICAL 3

void signExtend(char a[], char c[], int bits);
void onesComplement(char a[], char c[]);
void twosComplement(char a[], char c[]);
void binaryAdd(char a[], char b[], char c[]);
void zeroArray(char a[], int length);
void blankArray(char a[], int length);
int arrayLength(char a[]);
void shift(char a[], int type);
int compareBinary(char a[], char b[]);



void shift(char a[], int type){
    int length = 16; //arrayLength(a);
    int i;

    switch(type){
        case SHIFT_RIGHT_ARITHMETIC:
            for(i=0;i<length-1;i++){
                a[i]=a[i+1];
            }
            break;
        case SHIFT_RIGHT_LOGICAL:
            for(i=0;i<length-1;i++){
                a[i]=a[i+1];
            }
            a[length-1]='0';
            break;
        case SHIFT_LEFT_LOGICAL:
            for(i=length-1;i>0;i--){
                a[i]=a[i-1];
            }
            a[0]='0';
            break;
    }
    return;
}

void signExtend(char a[], char c[], int bits){
    char carryBit='0';
    int i;

    for(i=0;i<bits;i++){
        if(a[i]=='0'||a[i]=='1'){
            c[i-1]=a[i];
            carryBit=a[i];
        }
        else{
            c[i-1]=carryBit;
        }
    }
    return;
}

void onesComplement(char a[], char c[]){
    int i;
    //ones complement of a
    for(i=0;i<16;i++){
        if(a[i]=='0'){
            c[i]='1';
        }
        else{
            c[i]='0';
        }
    }
    return;
}

void twosComplement(char a[], char c[]){
    char temp[16];
    char addone[16];
    int i;

    blankArray(temp,16);
    addone[0]='1';
    for(i=1;i<16;i++)
        addone[i]='0';


    onesComplement(a,temp);
    binaryAdd(temp,addone,c);

    return;
}

void binaryAdd(char a[], char b[], char c[]){
    char carryBit='0';
    int i,j;

    for(i=0;i<16;i++){
        if( (a[i]=='0' && b[i]=='0' && carryBit=='0') ){
            carryBit='0';
            c[i]='0';
        }

        else if((a[i]=='1' && b[i]=='0' && carryBit=='0') ||
                (a[i]=='0' && b[i]=='1' && carryBit=='0') ||
                (a[i]=='0' && b[i]=='0' && carryBit=='1')){
            carryBit='0';
            c[i]='1';
        }
        else if(a[i]=='1' && b[i]=='1' && carryBit=='1'){
            carryBit='1';
            c[i]='1';
        }
        else{
            carryBit='1';
            c[i]='0';
        }
    }
    return;
}


int arrayLength(char a[]){
    int length=0;
    while(a[length]=='0' || a[length]=='1'){
        length++;
    }
    return length;
}

void getBinary(char ret[], char variableName){
    char input[17], temp[17];
    int i,j;


/*  for(i=0; i<16; i++){
        input[i]='\0';
        temp[i]='\0';
    }
    input[17]='\0';
    */

    blankArray(input, 17);
    blankArray(temp, 17);


    cout << "Input "<< variableName <<" in binary: ";
    cin.getline(input,17);


    int l=arrayLength(input);
    cout << l <<endl;
    for(i=0;i<=l;i++){
            temp[i]=input[l-i];
    }

/*    int j;
    for(j=0;j<16;j++){
    for(i=0;i<j;i++){
        cout << temp[i];
    }
    cout<<endl;
    }
*/

    signExtend(temp,ret,17);


}

void zeroArray(char a[], int length){
    int i;

    for(i=0; i<length; i++){
        a[i]='0';
    }

    return;
}


void blankArray(char a[], int length){
    int i;

    for(i=0; i<length; i++){
        a[i]='\0';
    }

    return;
}


void binaryDivide(char a[], char b[], char c[], char d[]){
    char signA, signB, signC, signD;
    int i, j, aMSB, bMSB;
    char dividend[16], divisor[16], quotient[16], remainder[16];
    char temp[16],temp2[16];
    char aWork[16], bWork[16], cWork[16];

    //begin the binary division.
    signA=a[15];
    signB=b[15];

    if((signA=='0'&& signB=='0')||(signA=='1'&& signB=='1')){
        signC='0';
    }else{
        signC='1';
    }

    //decide if the dividend and quotient need reversal
    for(i=0;i<16;i++){
        dividend[i]=a[i];
        divisor[i]=b[i];
    }

    //find MSBs
    for(i=15;i>=0;i--){
        if(a[i]=='1'){
            aMSB=i;
            i=-1;
        }
    }
    for(i=15;i>=0;i--){
        if(b[i]=='1'){
            bMSB=i;
            i=-1;
        }
    }



    int aHighIndex=aMSB;
    int aLowIndex=aMSB-bMSB;
    int cLimit=aLowIndex+1;

    for(i=0; i<16; i++) aWork[i]='0';
    for(i=0; i<16; i++) bWork[i]='0';
    for(i=0; i<16; i++) cWork[i]='0';


    j=bMSB;
    for(i=aMSB;i>=aLowIndex;i--){
        aWork[j--]=a[i];
    }

    j=bMSB;
    for(i=bMSB;i>=0;i--){
        bWork[j--]=b[i];
    }

    //begin binary division
    do{
        //determine if dividend is larger than divisor.


        int isLarger=compareBinary(aWork,bWork);
        if(isLarger>=0){
            cWork[aLowIndex]='1';
            blankArray(temp,16);
            blankArray(temp2,16);
            twosComplement(bWork,temp);
            binaryAdd(aWork,temp,temp2);
            for(i=15;i>=0;i--)  aWork[i]=temp2[i];
        }
        else{
            cWork[aLowIndex]='0';
        }

        //aHighIndex--;
        aLowIndex--;

        //now, transfer the result, temp2, to aWork to begin again.
        //blankArray(aWork,16);

//        for(i=15;i>=0;i--)  aWork[i]=temp2[i];

        if(aLowIndex>=0){
            shift(aWork,SHIFT_LEFT_LOGICAL);
            aWork[0]=a[aLowIndex];
        }
        cLimit--;
    } while (aLowIndex>=0);

    for(i=15;i>=0;i--) d[i]=aWork[i];
    for(i=15;i>=0;i--) c[i]=cWork[i];

    return;
}

/**
  * Returns 1 if A>B.
  * Returns 0 if A=B.
  * Returns -1 if A<B.
  */
int compareBinary(char a[], char b[]){
    int i, aMSB, bMSB;


    for(i=15;i>=0;i--){
        if(a[i]=='1'){
            aMSB=i;
            i=-1;
        }
    }
    for(i=15;i>=0;i--){
        if(b[i]=='1'){
            bMSB=i;
            i=-1;
        }
    }

    for(i=15;i>=0;i--){
        //if we have a 1 in a bit more significant than bMSB, dividend is larger.
        if(a[i]=='1' && i>bMSB){
            return 1;
        }
        else if(b[i]=='1' && i>aMSB){
            return -1;
        }
        //if not...
        else{
            //if we have a 1 in A and a 0 in B, the dividend is larger.
            if(a[i]=='1' && b[i]=='0'){
                return 1;
            }
            //if A=0 and B=1, the divisor is larger.
            else if(a[i]=='0' && b[i]=='1'){
                return -1;
            }
        }
    }
    return 0;
}


int binaryToDecimal(char a[]){
    int decimal=0;
    int i;
    char temp[16];

    for (i=0; i<16; i++){
        temp[i]=a[i];
    }

    if(a[15]=='1'){
        twosComplement(a,temp);
    }

    for (i=0; i<16; i++){
        if(temp[i]=='1'){
            decimal += 1*(int)pow(2.0,i);
        }
    }

    if(a[15]=='1'){
        decimal = (-decimal);
    }

    return decimal;
}


int main(int argc, char *argv[])
{
    char a[16], b[16], c[16], d[16];
    int i;
    string inputStr;

//    for(i=0; i<16; i++){
//        a[i]='\0';
//        b[i]='\0';
//    }
    blankArray(a, 16);
    blankArray(b, 16);
    blankArray(c, 16);
    blankArray(d, 16);

    cout << "Take note that any values beginning with '1' will be treated ";
    cout << "as negative." << endl;

    getBinary(a,'A');
    getBinary(b,'B');

    binaryDivide(a,b,c,d);
    //twosComplement(a,c);


//testing

    cout << "A: " << binaryToDecimal(a) << "\t";
    for(i=15;i>=0;i--)
        cout << a[i];
    cout << endl;
    cout << "B: " << binaryToDecimal(b) << "\t";
    for(i=15;i>=0;i--)
        cout << b[i];
    cout << endl;
    cout << "C: " << binaryToDecimal(c) << "\t";
    for(i=15;i>=0;i--)
        cout << c[i];
    cout << endl;
    cout << "D: " << binaryToDecimal(d) << "\t";
    for(i=15;i>=0;i--)
        cout << d[i];
    cout << endl;


    cout << endl << endl;
    i=compareBinary(a,b);

    cout << binaryToDecimal(a) << " is ";
    switch(i){
        case -1:
            cout << "smaller than ";
            break;
        case 0:
            cout << "equal to ";
            break;
        case 1:
            cout << "larger than ";
            break;
    }
    cout << binaryToDecimal(b) << endl;


    system("PAUSE");
    return EXIT_SUCCESS;
}