Bitwise Operations Part I

This is the first artical on Bitwise Operation, and today I will discuss how to multiple numbers using bitwise operation.

Before we dwell in the multiplication lets do some quick overview of bitwise left shift operations. Left shift operator is represented by ‘<<’.

Whenever we left shift a number by 1 we move each bit present at position x to position x+1, and append 0 at the position zero (Also, known as LSB.)
Left shift example:

E.g.:

Left shift 13 by 1.
13 is represented as 1101
13 << 1 = 11010

Similarly we want to left shift something by 5 digits, each bit is moved 5 positions to left and last 5 LSB bits are replaced with zero.

13 << 5= 110100000

For multiplication we only need to know about left shift so lets get started.

Example 1: Multiple 13 and 2 To multiply any number represented in binary we need to left shift the number by 1. So, if we want to multiply 13 by 2 we just need to perform 1 operation.
 i.e. 13 << 1
The above operation produces: 11010, which is equivalent to 26 ( 13*2 = 26 )in decimal.

Example 2:  Calculate 170* 2
Binary of 170 is 10101010
Left shift 10101010 < 1 = 101010100 ( 340 in decimal )

Conclusion: Left shift a number by 1 to multiply a number by 2.

The above method can be extended multiply a number by 4,8,16,32 and so on… So, if you want to multiple a number  ‘x’ by 4, multiply the number x with 2, 2 times.
I.e.:

x<<1      // to get x*2 and again
x<<1      //to get x*2*2
/*  The above expression is equivalent to x<<2. */

In general, if we want to multiple a number ‘x’ with another number which can be represented as 2^n, we can get the result by doing x<<n. ( Left shit x by n ) Multiplying x with y, where x  > 1 and y > 1 In binary each bit can take 2 values 0 or 1 and each bit correspond to value which can be determined as follows: If the bit at position n is set, it means that that set bit add 2^n to the total value of the number.

E.g.:

=  1     0     0     1     0      0     0     1 

= 2^7   2^6   2^5   2^4   2^3   2^2   2^1  2^0

= 128   0     0     16    0     0     0    1

= 128 + 16 + 1

= 145

So if we want to multiple any number ‘x’ with 145, how do we calculate the result using bitwise operation.
To demonstrate the working we will multiply 11 with 145 (Result should be 1595.)
In the binary representation of 145, bits at position 7, 4, 0  (0 based positioning. )

Calculation:

= 11 * 145

= 11 * (2^7 + 2^4 + 2^0)

= 1011 * (2^7 + 2^4 + 2^0)              // 11 in binary is 1011

= 1011 * 2^7  + 1011 * 2^4 + 1011 * 2^0 

= 1011 <<7 + 1011 << 4 + 1011 << 0      

= 10110000000 + 10110000 + 1011   

= 11000111011                           // 1595 in binary

= 1595

So to get the result we need to represent the number in terms of power of two.  And then use the bitwise operation and addition to get the result of a complicated multiplication.

GCD and LCM

We learned about LCM and GCD in our 6/7th Standard. The example on WikiPedia explains the GCD, the way we learn it in school.
First, we represent both the number as product of prime numbers.
Then pick the common number, which appear in both the product representation.
Finally, we multiply all the common factors to get the GCD.


Writing a program to calculate GCD based on above algorithm can be a complex and sometimes very slow. Luckily there are algorithms and trick to calculate GCD.

LCM also follows somewhat similar calculation, but if we know the GCD of the 2 numbers we can easilt calculate LCM using 3 simple steps.
1) Calculate product of 2 given numbers.
2) Calculate GCD of those 2 numbers.
3) Divide the product by GCD and we get LCM given 2 numbers.

Here is a simple code in C++ to calculate LCM and GCD using Euclidean algorithm
 

#include <iostream>
#include <assert.h>

using namespace std;

namespace Math {

    int gcd ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        if ( low == 1 || low == high )
            return low;

        int remainder = high % low;

        if ( remainder == 0 ) {
            return low;
        }
        high = low;
        low = remainder;
        return gcd( high, low );
    }

     int lcm ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        long product = low * high;
        int gcd = Math::gcd ( high, low );

        return product/gcd;
     }
}

using namespace Math;

int main ( int argc, char* argv[] ) {

  int int_gcd, int_lcm;

  int_gcd = gcd( 20, 10 );
  assert( int_gcd == 10 );
  printf( "GCD( %d, %d) = %d \n", 20, 10, int_gcd );
  int_gcd = gcd( 95, 5 );
  assert ( int_gcd == 5 );
  printf( "GCD( %d, %d) = %d \n", 95, 5, int_gcd );

  int_gcd = gcd ( 49, 14 );
  assert ( int_gcd == 7 );
  printf( "GCD( %d, %d) = %d \n", 49, 14, int_gcd );

 int_lcm = lcm ( 100, 10 );
  printf( "LCM( %d, %d) = %d \n", 100, 10, int_lcm );

  int_lcm = lcm ( 218912312, 67223434 );
  printf( "LCM( %d, %d) = %d \n", 218912312, 67223434, int_lcm );

}

Above program produces following output:

GCD( 20, 10) = 10 
GCD( 95, 5) = 5 
GCD( 49, 14) = 7 
LCM( 100, 10) = 100 
LCM( 218912312, 67223434 ) = 966336792

Refreneces: GCD LCM Euclidean algorithm

Sort linked list.

I found an interesting problem about the linked list and decided that I should try to solve this problem.

The problem statement was
Given a linked list: 1->9->3->8->5->7->7
 

 Find the pattern in the above linked link
 sort the linked list.

BTW, The pattern is odd elements in the linked list are in increasing order and even elements are decreasing order.

Sorting the above linked list is like sorting any other linked list and we could use several known methods. But since the input is already sorted, we should not try use the property. Sorting an already sorted input is always a bad approach.

This problem can be solved in several ways, the 2 approaches that I came up with are:

Method 1:
- Point nth odd element to n+1th odd element.
- Use a stack and push all the even elements on the stack until we reach end of the list.
- Once we are reach the end of the list, we can pop the elements from stack and stick them at the end of the linked list.
- Done

Method 2:
1) Again, Point nth odd element to n+1th odd element.  ( Even_list )
2) Save the next even element, so we dont loose it when we perform the step 1)
3) Now point n+1th even element to nth even element. ( Odd_list )
4) Merge odd_list  and Even_list
5) Done

Here is the code for Method 2 in C++.

#include<iostream>
#include<assert.h>
#include<fstream>

using namespace std;

class Node {
  public:
    Node( int value );
    int data;
    Node* next;
};

Node::Node( int value ) {
  data = value;
  next = NULL;
};

class List {

public:
  void add_node( int value );
  void print_list();
  void sort_list();
  List();

private:

  Node* head;
  Node* end;

  void _merge_lists( Node* &head,  Node* &even_list, Node* &odd_list );
  void _print_list( Node *iter);
  void _sort_list( Node * &subroot, Node * &even_list, Node* &odd_list, int &count ) ;
  void _merge( Node* &subroot, Node* &even_list, Node* &odd_list );
};

List::List() {
  head = NULL;
  end = head;
};

void List::add_node( int val ) {

  Node* new_node = new Node( val );

  if( head == NULL ) {
    head = new_node;
    end = head;
  } 
  else {
    end->next = new_node;
    end = end->next;
  }
}

void List::print_list() {
  Node* iter  = head;
  _print_list( iter );
}

void List::_print_list( Node *iter ) {
  while( iter != NULL ){
    printf( "%d", iter->data);
    if ( iter->next != NULL )
      printf("->");
    iter = iter->next;
  }
  printf("\n");
}

void List::_merge_lists( Node* &head, Node* &even_list, Node* &odd_list ) {

  assert( even_list!= NULL );
  assert ( head != NULL );

  if ( odd_list != NULL && even_list->data > odd_list->data ) {
    head = odd_list;
    odd_list = odd_list->next;
  }
  else {
    head = even_list;
    even_list = even_list->next;
  }

  Node* subroot = head;
  _merge( subroot, even_list, odd_list );
}

void List::_merge( Node* &subroot, Node* &even_list, Node* &odd_list ) {

  assert( subroot != NULL );

  if ( odd_list == NULL && even_list == NULL ) {
    return;
  }
  if( odd_list == NULL ) {
    subroot->next =  even_list;
    return;
  }
  else {
    if ( even_list == NULL ) {
    subroot->next = odd_list;
    return;
    }
    else {
      assert ( even_list != NULL );
      assert( odd_list != NULL );

      if ( even_list->data < odd_list->data ) {
    subroot->next = even_list;
    even_list = even_list->next;
      }
      else {
    subroot->next = odd_list;
    odd_list = odd_list->next;
      }
      subroot = subroot->next;
      _merge( subroot, even_list, odd_list );
    }
  }
}

void List::sort_list(){
  
  Node* even_list = NULL;
  Node* odd_list = NULL;
  int count = 0;
  _sort_list( head, even_list, odd_list, count );  

  even_list = head;
  _merge_lists( head, even_list, odd_list );
}


void List::_sort_list( Node* &subroot, Node* &even_list, Node* &odd_list, int &count ) {

  if ( subroot == NULL ) {
    return;
  }

  Node* next_node = subroot->next;

  // even elements, 0,2,.....
  if ( count % 2 == 0 ) {
    if ( even_list == NULL ) {
      even_list = subroot;
      even_list->next = NULL;
    }
    else {
      even_list->next  = subroot;
      even_list = even_list->next;
      even_list->next = NULL;
    }
  }
  // Odd element
  else {
    if ( odd_list == NULL ) {
      odd_list = subroot;
      odd_list->next = NULL;
    }
    else {
      subroot->next = odd_list;
      odd_list = subroot;
    }
  }
  _sort_list( next_node, even_list, odd_list, ++count );
}

Feel free to comment if there are any bugs in the code or it does not work on a given case.

Implement FIFO queue using Arrays

Queue are very basic data structures in computer science and there are multiple variation of Queue.  They simplest  one being FIFO (http://en.wikipedia.org/wiki/FIFO) queue. The other well known queue is priority queue (http://en.wikipedia.org/wiki/Priority_queue ).

FIFO queues can be implemented using array or linked list and each implementation has some advantage over the other.
E.g.:
-  If implemented using arrays. dequeue and enqueue operation be performed in O(1), but adds the limitation on the queue size.
- Linked list, overcome the size limitation and keeps the dequeue and enqueue operation to 0(1).
- We can use modern advance data structures such as vectors ( Dynamic arrays ) to implement queues, but whenever the existing capacity for vector is reached, a new vector of size of 2n is created and all the elements from old vector is copied to newly allocated vector.

Implementing FIFO queue is always preferred to be implemented in Linked List, but some time candidates are asked to implement a variation of the FIFO.
E.g.: 1) Use Array/Vector to implement queue.
         2) Use stacks to implement queue.( Cracking the coding interview has the answers for this. )

Queue have very simple characteristics:
1) enqueue: add a new element at the end of the queue.
2) dequeue: remove an element from the from of the queue,

I wanted to implemented the array version and here is what I came up with.

#include <iostream>
#include <stdlib.h>

using namespace std;

enum queue_code {
    QUEUE_EMPTY = 0,
    QUEUE_FULL,
    QUEUE_SUCCESS
};

class Queue{

 public:
  queue_code enqueue( int value );
  queue_code dequeue( int &queue_element );
  Queue();
  Queue(int size);
  ~Queue();
 private:
  int queue_capacity;
  int *queue;
  int queue_end;
  int queue_start;
  int queue_size;

};

queue_code Queue::enqueue( int value ) {
    if ( queue_size == queue_capacity ) {
      return QUEUE_FULL;
    }

    queue[queue_end] = value;
    queue_end = (   queue_end ) % queue_capacity;
    queue_size  ;
    return QUEUE_SUCCESS;
};

queue_code Queue::dequeue( int &queue_element ) {
    if ( queue_size == 0 ) {
      return QUEUE_EMPTY;
    }
    queue_element  = queue[queue_start];
    queue_start    = (   queue_start ) % queue_capacity; 
    queue_size--;
    return QUEUE_SUCCESS;
};
  
Queue::Queue ( int size ) {
    queue_capacity = size;
    queue = new int[ queue_capacity ];
    queue_end = 0;
    queue_start = 0;
    queue_size = 0;
};

Queue::~Queue() {
  delete[] queue;
}

I hope this was hopeful.

Interia

Starting to write something from scratch is always been hard for me and I am sure there are number of people like me who need that first push. And probably some of you are reading this post at this moment.

I was waiting for the right time to start the blog  and the right topic.
I always thought this is not the right time to start a blog or I don't have a good topic to write about. Whichever topic I thought I would write about, there was already an article about it, and perhaps it was some expert in that field. And If I don't write about the topic that's not already present on the internet I think I will never write anything about any topic.

So I just asked myself, Am I writing this for "everyone on the this planet" or "For myself and few others who share the same interest?".  I quickly realized that I am writing for the later, but I can not ignore the former. I mean once I post this blog, its accessible to everyone who has internet access and interested in field I like to write about. And all the friends of mine who share the same interests will find this blog eventually.

So I told myself, I shouldn't worry about Who is going to read it and who is not?.  Just start writing it.

So here I am with the force I was waiting for last few years to push me and get started with this part of my life.