Saturday, June 18, 2011

LOGIC GATES (NOT, AND, OR, XOR)



What is a LOGIC GATE

A logic gate is an elementary building block of a digital circuit . Most logic gates have two inputs and one output. At any given moment, every terminal is in one of the two binary conditions low (0) or high (1), represented by different voltage levels. The logic state of a terminal can, and generally does, change often, as the circuit processes data. In most logic gates, the low state is approximately zero volts (0 V), while the high state is approximately five volts positive (+5 V).

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and XNOR.


NOT LOGIC GATE

This gate has one input and one output. The output is high when input is low and vice-versa The diagram is shown below


 
Inverter or NOT gate


TRUTH TABLE OF NOT GATE
Input
Output
1
0
0
1

AND GATE

This logic gate has two or more inputs and one output. The output is high only when all the inputs are high.
  
/WhatIs/images/and.gif (220 bytes)
AND gate

  
TRUTH TABLE OF AND GATE
Input 1
Input 2
Output
0
0
0
0
1
0
1
0
0
1
1
1



OR GATE
OR gate has two or more input and one output. The output is high for any of the input being high.

/WhatIs/images/or.gif (224 bytes)
OR gate

                                        TRUTH TABLE FOR OR GATE
Input 1
Input 2
Output
0
0
0
0
1
1
1
0
1
1
1
1


XOR GATE

The XOR ( exclusive-OR )  gate has two or more inputs and one output. The output is low for the inputs being same and the output is high for the input being different.



         
XOR gate

TRUTH TABLE OF XOR GATE

Input 1
Input 2
Output
0
0
0
0
1
1
1
0
1
1
1
0

What are the use of Logic gates ?


Logic gates are in fact the building block of digital electronics; they are formed by the combination of transistors (either BJT or MOSFET) to realize some digital operations (like logical OR, AND, INVERT ). Every digital product, like computers, mobile, calculators even digital watches, contain logic gates. The use of logic gates in digital world can be understood better by the following example: the single bit full adder in digital electronics is a logic circuit which perform the logical addition of two single bit binary numbers (a,b,cin) a and b are the the two binary number of single digit (either 1 or 0) and cin is the carry input . say for example a,b,cin= 1,1,1 gave an logical sum output of 1 and a carry of 1 , a,b,cin= 110 gave sum= 0 and carry of 1. Now this adder can be formed by the combination of many gate like by using NAND gates only. or by using XOR , AND ,OR gates and so on. So, in a nutshell, the adder which is of great importance in your computer processor and also in many more applications is basically built from the logic gates.

Monday, June 6, 2011

Binary Search Algorithm + Program

What is binary search ?

Binary search starts by searching of the data in the elements at the mid of the array to determine if the target is in the first or second half of the list. If it is in the first half we do not need to check the second half. If its in the second half we need not check the first half. In other words we estimate half the list from further consideration. We repeat this process until we find the target or determine that it is not in the list.

Binary Search only works for the sorted array. Binary search is a Divide and Conquer technique.




Binary search algorithm:

algorithm binarySearch ()
Return found <Boolean>
first = 0
last = end
loop (first <= last )
   mid = (first + last)/2
   if (target > list [ mid ] )
   LOOK IN UPPER HALF
   first = mid + 1
   else if (target < list [mid])
   LOOK IN LOWER HALF
   last = mid -1
   else
   Found equal : force exit
   first = last + 1
   end if
end loop
locn = mid
if (target equal list mid [mid])
   found = true
   else
   found = false
   end if
   return found
end binarySearch



//TO WRITE A PROGRAM TO SEARCH FOR A GIVEN ELEMENT FROM AN ARRAY USING BINARY SEARCH

//SEARCH TECHNIQUE

#include<iostream.h>
#include<conio.h>


void binsearch(int ar[],int size,int ele)
{       int lb=0,ub=size-1,mid;             //lb=>lower bound,ub=>upper bound

     for(;lb<ub;)
       {
           mid=(lb+ub)/2;

           if(ar[mid]==ele)
             {
                cout<<"\n SEARCH SUCCESSFUL";
                break;
             }

           else
                 if(ar[mid]<ele)
                 ub=mid-1;

           else
               if(ar[mid]>ele)
                  lb=mid+1;
      }

       if(ub<lb)

         cout<<"\n SEARCH UNSUCCESSFUL";

}

void sort(int ar[],int size)               //sorts the array in ascending array using bubble sort
{
     int temp;

     for(int i=0;i<size;i++)
         for(int j=0;j<size-i-1;j++)
          if(ar[j]>ar[j+1])
               {
                temp=ar[j];
                ar[j]=ar[j+1];
                ar[j+1]=temp;

               }

}

void display(int ar[],int size)
{
     for(int i=0;i<size;i++)
         cout<<'\n'<<ar[i];
}

void input(int ar[],int size)
{
     for(int i=0;i<size;i++)
         cin>>ar[i];
}

void main()
{
     clrscr();

     int size;
     cout<<"\n ENTER THE NUMBER OF ELEMENTS REQUIRED IN THE ARRAY :";
     cin>>size;

     int *ar=new int(size);

     cout<<"\n ENTER THE ELEMENTS OF THE ARRAY :\n";

     input(ar,size);         //takes the input from the array

     sort(ar,size);         //sorts the array in the ascending order

     int ele;
     cout<<"\n ENTER THE ELEMENT TO BE FOUND :\n";
     cin>>ele;

     getch();

}
Subscribe to: Posts (Atom)