Operation on Bits and Bitwise Operators

OK guys, this is my first post in the New Year 2008, I thought of posting it
earlier but at last I didn’t. It’s already been so long since I
posted so let’s keep everything aside and talk just about what we have
for today. ;-)

I was sitting the other day thinking about what to write for a post here. Suddenly
I realized that we have discussed operations
on matrices, arrays,
and what not but we haven’t had the chance to talk anything about the
most fundamental thing a computer understands. Yeah, Operation on Bits.

Bits can have only two values either ON (1) or OFF (0). In this article, we’ll
be discussing about the different operations which can be performed on bits.
One thing to note here is, we don’t perform these operation on single
bits but rather on a group of bits (byte(s)). So even though Bitwise operators
operate on bits its almost always a part of a group (byte, which makes up each
data type), it means we can do bitwise operations on any data type.

BTW, the operators that perform operation on bits are called Bitwise Operator
and such operations are known as Bitwise Operations

The six bitwise operators are listed below:

&	AND
|	OR
^	XOR
>>	Right shift
<<	Left shift
~	One’s complement

For this post we’ll only be discussing &(AND) and | (OR) operators
leaving the rest for future posts ;-)

Bitwise AND (&) Operator: First thing, it’s nothing to do with the
Logical (&&) operator, both are different.

Now, if you know something about Logic Gates then you might already know about
this. For the rest of us, it does an AND mask on bits.

So, suppose if we have two separate bytes having binary values as 00100000
and 00100001 then doing AND operation would give us the following result.

First Byte: Second Byte:	00100000 00100001
Result:	00100000

The truth table for this would be:

First Bit	Second Bit	& (AND)
1 1 0 0	1 0 1 0	1 0 0 0

As the Logic AND Gate does, it takes two bits (from the two separate bytes)
and if both of them are ON (1) then only it gives ON (1) in all other cases
it gives OFF (0). So starting from the right there is 0&1->0, 0&0->0,…,
1&1->1 and so on.

Bitwise OR (|) Operator: Here again, both OR (||) and Bitwise OR (|) are different.

The following example is sufficient for you all to understand its operation.

First Byte: Second Byte:	00100000 00100001
Result:	00100001

Truth table

First Bit	Second Bit	& (OR)
1 1 0 0	1 0 1 0	1 1 1 0

There won’t be any example program here because to fully understand these
operators we need to express data as bits (binary form) and see how the operations
change them. Since decimal to binary conversion programs require some bitwise
operations that we’ve yet to discuss so I think it’ll be pointless
to have such programs now!

P.S. An integer in 32-Bit (Windows) environment is 4 bytes long. Short int
is half of that

8 bits make up one byte.

Related Articles:

• 
  

  C++
  Data Types in Detail

  
  


• 
  

  Problems
  on Operator Overloading II

  
  


• 
  

  Class
  with all the Overloaded Arithmetic Operators

  
  


• 
  

  Overloading
  Post-Fix Forms of ++ and -- Operators

  
  

Using a Stack to Reverse Numbers

Yeah, I heard many of you saying this and I know it’s no big deal to
reverse a number and neither is it using stack to do so. I am writing this just
to give you an example of how certain things in a program can be done using
stacks. So, let’s move on…

As many of you already know, a stack is a Data Structure in which data can
be added and retrieved both from only one end (same end). Data is stored linearly
and the last data added is the first one to be retrieved, due to this fact it
is also known as Last-In-First-Out data structure. For more info please read
Data
Structures: Introduction to Stacks.

Now, let’s talk about reversing a number, well reversing means to rearrange
a number in the opposite order from one end to the other.

Suppose we have a number

12345

then its reverse will be

54321

Ok, now let’s have a look at the example program which does this:

  // Program in C++ to reverse
  // a number using a Stack

  // PUSH -> Adding data to the sat ck
  // POP -> Retrieving data from the stack

  #include<iostream.h>

  // stack class
  class stack
  {
    int arr[100];
    // 'top' will hold the
    // index number in the
    // array from which all
    // the pushing and popping
    // will be done
    int top;
  public:
    stack();
    void push(int);
    int pop();
  };


  // member functions
  // of the stack class
  stack::stack()
  {
    // initialize the top
    // position
    top=-1;
  }

  void stack::push(int num)
  {
    if(top==100)
    {
      cout<<"\nStack Full!\n";
      return;
    }

    top++;
    arr[top]=num;
  }

  int stack::pop()
  {
    if(top==-1)
    {
      return NULL;
    }

    return arr[top--];
  }
  // member function definition ends

  void main()
  {
    stack st;
    int num, rev_num=0;
    int i=1, tmp;

    cout<<"Enter Number: ";
    cin>>num;

    // this code will store
    // the individual digits
    // of the number in the
    // Stack
    while(num>0)
    {
      st.push(num%10);
      num/=10;
    }

    // code below will retrieve
    // digits from the stack
    // to create the reversed
    // number
    tmp=st.pop();
    while(tmp!=NULL)
    {
      rev_num+=(tmp*i);
      tmp=st.pop();
      i*=10;
    }

    cout<<"Reverse: "<<rev_num<<endl;
  }

The above code is pretty much straightforward and I leave it up to you to understand
it!

P.S. If you experience any problems understanding it please first read the
article Data
Structures: Introduction to Stacks

Related Articles:

• 
  

  Data
  Structures: Introduction to Stacks

  
  


• 
  

  Data
  Structures: Introduction to Queues

  
  


• 
  

  Insertion
  and Deletion of elements in an Array

  
  

Introduction to Linked Stacks

In the article Data
Structures: Introduction to Stacks, we saw that there was one major
disadvantage of representing stacks using arrays- the stack like the array could
have a limited number of elements, while stacks should be able to grow up to
any number of elements. Besides this there were other disadvantages too.

In one of the other article about Linked
Lists, we noticed one useful property of linked lists that they can
grow up to any size to accommodate for the addition of elements and it efficiently
uses the memory too.

So if we combine both of this to from a linked version of the stack then it
won’t have the shortcomings that the array version had.

This is what this article is all about.

pushing and popping

As you know that addition of elements to the stack is known as pushing while
retrieval is known as popping.

The process of pushing and popping in case of linked version of stack is slightly
different from the array version. The following graphics will clear it though!

FIG: pushing of elements in the linked stack

FIG: popping of the elements from the linked
stack

Now that you know how the basic operations are performed on linked stacks I
present you with the example program to illustrate this.

As always I would strongly recommend you to read the comments!

  // -- Linked stacks --
  // Example program to 
  // illustrate basic
  // push and pop to a
  // linked stack
  #include<iostream.h>

  // node class, this will
  // represent the nodes or elements
  // of the linked stacks
  class node
  {
   public:
     int info;
     node *link;
  };

  // declare global objects
  node *start=NULL;

  // function prototypes
  void push(int);
  int pop();

  void main(void)
  {
   int ch=0,num;

   while(ch!=3)
   {
    cout<<"1> Push";
    cout<<"\n2> Pop";
    cout<<"\n3> Quit\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;

     push(num);
     break;

     case 2:
     cout<<"\n\nPopped: ";
     cout<<pop();
     cout<<"\n\n";
     break;
    }
   }

  // below is a bit confusing
  // part.
  // here all the nodes that
  // we have allocated are
  // being freed up
  node temp;
  while(start!=NULL)
  {
   // store the next node
   // to the one being deleted
   temp=*start;
   // delete the node
   delete start;

   // retrieve the next node
   // to be deleted
   start=temp.link;
   }
  }

  // pushes an element 'inf'
  // to the linked stack
  void push(int inf)
  {
   node *temp1;
   node temp2;

   // if the element to be added
   // is the first element of 
   // linked stack
   if(start==NULL)
   {
    // allocate a new node
    temp1=new node;
    temp1->info=inf;
    temp1->link=NULL;

    // make start point at it
    start=temp1;
   }
   // if not
   else
   {
    // store the information
    // about the node pointed
    // by 'start'
    temp2.info=start->info;
    temp2.link=start;

    temp1=new node;
    temp1->info=inf;
    // insert the new node
    // at the beginning
    // and make its link
    // point to the prev.
    // node pointed by 'start'
    temp1->link=temp2.link;

    start=temp1;
   }
  }

  // returns an element from the
  // linked stack
  int pop()
  {
   node temp;

   if(start!=NULL)
   {
    // store info. about
    // the first element
    // that has to be pooped
    temp=*start;

    // delete the node
    delete start;
    // make start point at the
    // next node which had been
    // stored
    start=temp.link;

    return temp.info;
   }

   return NULL;
  }

Good-Bye!

Related Articles:

• 
  

  Data
  Structures: Introduction to Stacks

  
  


• 
  

  
  Data Structures: Introduction to Queues

  
  


• 
  

  Introduction
  to Linked Lists

  
  

Data Structures: Introduction to Queues

Queue is a linear data structure in which data can be added to one end and
retrieved from the other. Just like the queue of the real world, the data that
goes first into the queue is the first one to be retrieved. That is why queues
are sometimes called as First-In-First-Out data structure.

In case of queues, we saw that data is inserted both from one end but in case
of Queues; data is added to one end (known as REAR) and retrieved from the other
end (known as FRONT).

The data first added is the first one to be retrieved while in case of queues
the data last added is the first one to be retrieved.

A few points regarding Queues:

1. 
   

   Queues: It is a linear data structure; linked lists and
   arrays can represent it. Although representing queues with arrays have its
   shortcomings but due to simplicity, we will be representing queues with
   arrays in this article.

   
   


2. 
   

   Rear: A variable stores the index number in the array
   at which the new data will be added (in the queue).

   
   


3. 
   

   Front: It is a variable storing the index number in the
   array where the data will be retrieved.

   
   

Let us have look at the process of adding and retrieving data in the queue
with the help of an example.

Suppose we have a queue represented by an array queue [10], which is empty
to start with. The values of front and rear variable upon different actions
are mentioned in {}.

queue [10]=EMPTY {front=-1, rear=0}

add (5)

Now, queue [10] = 5 {front=0, rear=1}

add (10)

Now, queue [10] = 5, 10 {front=0, rear=2}

retrieve () [It returns 5]

Now, queue [10] = 10 {front=1, rear=2}

retrieve () [now it returns 10]

Now, queue [10] is again empty {front=-1, rear=-1}

In this way, a queue like a stack, can grow and shrink over time.

Now have a look at the following example program that illustrates all this
stuff:

  // -- A Queue Class in C++ --
  // example program in C++ to
  // illustrate queues represented
  // by arrays
  #include<iostream.h>

  // macro to hold the max
  // number of elements
  // in the queue
  #define MAX 10

  // queue class
  class queue
  {
   int arr[MAX];
   int front, rear;
 
  public:

   void add(int);
   int retrieve(void);
   queue();
  };
  // queue class ends

  // member functions
  queue::queue()  
  {
   // initialize index
   // variables
   front=-1;
   rear=0;
  }

  void queue::add(int data)
  {
   if(rear==MAX-1)
   {
    cout<<"QUEUE FULL!";
    return;
   }

   arr[rear]=data;
   // increase index
   // variable
   rear++;

   if(front=-1)
   front=0;
  }

  int queue::retrieve()
  {
   int data;
 
   if(front==-1)
   {
    cout<<"QUEUE EMPTY!";
    return NULL;
   }

   data=arr[front];
   arr[front]=0;
  
   // if both index variables
   // point to the same location
   // then start afresh
   if(front==rear-1)
   {
    front=-1;
    rear=0;
   }
   else
    front++;

   return data;
  }
  // member functions ends

  void main(void)
  {
   queue obj;
   int ch;
   int num;

   while(ch!=3)
   {
    cout<<"1> ADD";
    cout<<"\n2> RETRIVE";
    cout<<"\n3> QUIT\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;

     obj.add(num);
     break;

     case 2:
     cout<<"\n\nRetrieved: ";
     cout<<obj.retrieve();
     cout<<"\n\n";
     break;
    }
   }
  }

Good-Bye

Please do check back for updates!

Related Articles:

• 
  

  Data
  Structures: Introduction to Stacks

  
  

Data Structures: Introduction to Stacks

In the previous article, we saw how data is inserted and deleted in an array.
In that case we could insert data at any place throughout the array. However,
there are situations when we only need to add and retrieve data form the ends
of the array. Stacks are one of the examples of this.

Stacks are data structures in which data could be added and retrieved only
from one end (also known as the TOP of the stack). Suppose we insert 5, 6, 9
to the stack consecutively then while retrieving the first one to be retrieved
will be 9 then 6 and then 5. That is why stacks are also known as Last-In-First-Out
(or LIFO) structure.

A few terms regarding stacks:

• 
  

  Stack: Stack is a user-defined data structure. It is most
  commonly represented by linked-lists and arrays. In this article, we will
  be representing stacks with arrays.

  
  


• 
  

  Push: Adding data to the stack is known as pushing.

  
  


• 
  

  Pop: Retrieving data from the stack is known as popping.

  
  

Let us have look at this process with the help of an example. Suppose we have
a stack represented by an array stack [10], which is empty to start with.

push(5)

Now, stack [10] = 5

push(10)

Now, stack [10] = 5, 10

pop() [It returns    10]

Now, stack [10] = 5

pop() [now it returns 5]

Now, stack [10] is again empty

In this way, a stack can grow and shrink over time.

Example Program

The process is quite simple so we straightaway move on to the example program
in c++ that illustrates the implementation of stack.

In the following program, we have defined a class that has all the function
implemented to represent a stack.

  // Example Program in C++
  // to illustrate Stacks
  #include<iostream.h>

  // stack class
  class stack
  {
   int arr[100];
   // 'top' will hold the
   // index number in the
   // array from which all
   // the pushing and popping
   // will be done
   int top;

  public:
   stack();
   void push(int);
   int pop();
  };
  // stack class definition ends

  // member functions
  // of the stack class
  stack::stack()
  {
   // initialize the top
   // position
   top=-1;
  }

  void stack::push(int num)
  {
   if(top==3)
   {
    cout<<"\nStack Full!\n";
    return;
   }

   top++;
   arr[top]=num;
  }

  int stack::pop()
  {
   if(top==-1)
   {
    cout<<"\nStack Empty!\n";
    return NULL;
   }

   return arr[top--];
  }
  // member function definition ends

  void main(void)
  {
   stack s;
   int ch;
   int num;

   while(ch!=3)
   {
    cout<<"1> Push";
    cout<<"\n2> Pop";
    cout<<"\n3> Quit\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;

     s.push(num);
     break;

     case 2:
     cout<<"\n\nPopped: ";
     cout<<s.pop();
     cout<<"\n\n";
     break;
    }
   }
  }

Good-Bye!

Related Articles:

• 
  

  Data Structures: Introduction to Queues