Chapter 2: Basic Abstract Data Types. Problem 2.7

//2.7 -- implement a linked list to store a binary number. 
//each node should store one bit. 
//add a recursive operation to increment this binary number. 

#include <iostream>
#include <string>
using namespace std;

//each node stores one bit. 
struct NODE
{
    unsigned char bit; //The smallest data type in C is a char.
    NODE* next;
}; 

bool ValidateBinaryNumberString(const string& sBinaryNumberStr); 
int RecursiveIncBinaryNumber(NODE* node); 
void CreateListForBinaryNumber(NODE** head, const string& sBinaryNumberStr); 
void PrintBinaryNumber(NODE* head); 
void IncrementBinaryNumber(NODE** head); 
int RecursiveIncBinaryNumber(NODE* node);

void main()
{
    cout << "Enter the binary number --> " << endl;
    string sBinaryNumber; 
    cin >> sBinaryNumber; 
    if( !ValidateBinaryNumberString(sBinaryNumber) )
    {
        cout << "Binary number in invalid format. Valid number can contain only 1 or 0 characters." << endl;
        return;
    }
    //Lets create a linked list to represent this binary number. 
    //the MSB is stored in the head and LSB just before the tail.
    NODE* head = NULL;
    CreateListForBinaryNumber(&head, sBinaryNumber); 
    PrintBinaryNumber(head); 
    IncrementBinaryNumber(&head); 
    PrintBinaryNumber(head);
}

bool ValidateBinaryNumberString(const string& sBinaryNumberStr)
{
    if( !sBinaryNumberStr.length() )
        return false;

    for(int n=0; n<sBinaryNumberStr.length(); n++)
    {
        if( sBinaryNumberStr[n] != '0' && sBinaryNumberStr[n] != '1' )
           return false;
    }
    return true;
}    
    
void CreateListForBinaryNumber(NODE** head, const string& sBinaryNumberStr)
{
    if( !head )
        return; 
    if( !sBinaryNumberStr.length() )
        return;

    NODE* curr = NULL;

    for( int n=0; n<sBinaryNumberStr.length(); n++ )
    {
        NODE* newNode = new NODE;
        newNode->bit = sBinaryNumberStr[n] == '1' ? 1 : 0; 
        newNode->next = NULL;

        if( *head == NULL )
            *head = newNode;
        else
            curr->next = newNode;
        curr = newNode;
    }
}

void PrintBinaryNumber(NODE* head)
{
    if( !head )
        return; 

    cout << "Binary Number is --> " << endl;
    for( NODE* curr = head; curr != NULL; curr=curr->next )
    {
        if( curr->bit )
            cout << "1"; 
        else
            cout << "0";
    }
    cout << endl << "<-- End of Binary Number." << endl;
}

void IncrementBinaryNumber(NODE** head)
{
    if( !head )
        return; 

    int nBitToAdd = RecursiveIncBinaryNumber(*head); 
    //This takes care of the case where there is a carry over from the Most signinficant bit.
    if( nBitToAdd )
    {
        //We need to add a new node for this bit. 
        NODE* newNode = new NODE; 
        newNode->bit = 1;
        NODE* temp = *head; 
        *head = newNode;
        newNode->next = temp;
    }
}

//Recursively adds one to the binary number. 
//returns a 1 if there is a carry over otherwise 0. 
int RecursiveIncBinaryNumber(NODE* node)
{
    if( !node )
        return 0; 

    int nBitToAdd = 1; //This starts with 1 because we want to add 1 to the binary number.
    if( node->next )
        nBitToAdd = RecursiveIncBinaryNumber(node->next);

   if( nBitToAdd )
   {
        if( node->bit == 0 )
        {
            nBitToAdd = 0; 
             node->bit = 1;
        }
   }
   return nBitToAdd; 
}