AND and XOR Gate : Addition without using + sign

Have you ever wondered how does a computer do addition operation. It doesn't have any fingers on which it can count on like little kids do.

AND and XOR logic gates help computer to do addtion

Rules for addition for binary numbers
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = (1 carry over) 0

add 17 + 5
17 = 1 0 0 0 0 1
  5 = 0 0 0 1 0 1
---------------------
22 = 1 0 0 1 1 0

Truth table for XOR
x      y         x XOR y
0      0            0
0      1            1
1      0            1
1      1            0

We can see that addition of bits have similar behavior as XORing the two bits
To see whether there is a carry over we  need AND gate

Truth table for AND
x      y         x AND y
0      0            0
0      1            0
1      0            0
1      1            1

In C language ^ operator is bitwise XOR and & operator is bitwise AND
<< is the left shift operator
011010<<1 =110100 [each digit is shifted to left side and to the right a 0 digit is added] 

Addition without arithmetic operator +
Steps
1. sum = x XOR y
2. carry = x AND y
3. carry = carry << 1
4. x = sum
5. y = carry
6. Goto Step 1 if carry is not equal to 0.
7. If carry equal to 0 print sum

Example
let x = 15 = 1 1 1 1
let y =   9 = 1 0 0 1
sum  x^y =  0 1 1 0
carry x&y= 1 0 0 1

carry<<1 = 1 0 0 1 0 (carry not equal to 0, loop to begining)

x=sum         0 0 1 1 0
y=carry       1 0 0 1 0
sum x^y=    1 0 1 0 0
carry x&y=  0 0 0 1 0

carry<<1 =  0 0 1 0 0 (carry not equal to 0, loop to begining)

x=sum         1 0 1 0 0
y=carry       0 0 1 0 0
sum x^y=    1 0 0 0 0
carry x&y=  0 0 1 0 0

carry<<1 =  0 1 0 0 0 (carry not equal to 0, loop to begining)

x=sum         1 0 0 0 0
y=carry       0 1 0 0 0
sum x^y=    1 1 0 0 0
carry x&y=  0 0 0 0 0

carry<<1 =  0 0 0 0 0 (carry = 0 , go out of loop)

print sum = 1 1 0 0 0 = 24

#include<stdio.h>
int main()
{
    int x,y,sum, carry;
    int xcopy,ycopy;
    printf("\nEnter the two numbers:");
    scanf("%d%d",&x,&y);
    xcopy=x;
    ycopy=y;

    do
        {
         sum=x^y;
         carry=x&y;
         carry=carry<<1;
         x=sum;
         y=carry;
        }while(carry!=0);

      printf("%d + %d = %d", xcopy, ycopy, sum);
      return 0;
}


     

 

Finding H.C.F (Highest Common Factor) of two numbers : logic and program

Highest common factor(hcf) also know as greatest common divisor(gcd) is the largest common factor among the factors of two numbers
For example, find the hcf of 8,12
factors of 8= 1,2,4,8
factors of 12=1,2,3,4,6,12
hcf(8,12)=4

The process of finding hcf is more straight-forward and easy.
Dividend  Divisor  Remainder
12                8              4
8                  4              0
hcf(12,8)=4


Dividend  Divisor  Remainder
45               27             18
27               18             9
18                9              0
hcf(45,27)=9

Steps
1. Divide the bigger number by smaller number. and store the remainder
2. If remainder is equal to 0 then divisor is hcf.
3. If remainder is not equal to 0 then divisor becomes dividend and remainder becomes divisor
4. Goto step 2.

#include<stdio.h>
int hcf(int a,int b); /* Function Prototype */
int main()
{
        int x,y, h;
        printf("\nEnter two numbers:");
        scanf("%d%d",&x,&y);

        if (x<y)
             h=hcf(y,x);
        else
             h=hcf(x,y);

        printf("\nH.C.F(%d,%d)=%d",x,y,h);
        return 0;
}
int hcf(int a, int b)
{
         int rem;
         do
          {
                 rem=a%b;
                 a=b;
                 b=rem;
           }while(rem!=0);
          return a;
}

Modular Division or Remainder Division (% sign in C language)

Although I have already written many programs using modulo(modulus) division in the blog, yet i haven't explained it anywhere and relatively new programmers would be opening up some other reference pages to search what % sign means , I thought I can make life simpler for them including it here. Better late than never :)

So what a%b means in C
Say a = 35 and b = 8
35 when divided by 8 it gives quotient as 4 and remainder as 3.

In C language
35%8=3
24%4=0

We can also write it as 35=4*8+3

8%14?
8=0*14+8
Hence 8%14=8

(-5)modulo3?
possible.
 -5-(3*-1)=-2 .
make the remainder +ve by adding
-2+3=1
(-5)modulo3=1

But in gcc compiler
-5%3=-2
and
5%-3=2
and
-5%-3=-2

Program to find whether a number is prime or not

A prime number is one which is only divisible by itself or 1 and not by any other number.
Series of Prime numbers is given below
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ...  
The only even prime number is 2.

we can check for prime number by checking whether it is even or not. If it is not even, then we can set a loop to check it with series of odd numbers

Let 'n' be the given number
if(n==2)
{
it is prime;
return ; stop the program
}
if (n%2==0)
{
it is not prime
return ; stop the program
}
flag=0
for(i=3; i<n; i=i+2)
{
if ((n%i)==0)
{
then number is not prime because it is completely divisible by number other than itself or 1.
flag =1
break from loop; 
}
}
if flag == 0 then number is prime
else it is not prime

For example take given number =11
11 !=2
11%2 !=0
value of i    computation       loop count
3                   11%2 != 0            1
5                   11%3 != 0            2
7                   11%4 != 0            3
9                   11%5 != 0            4

Hence 11 is prime.

Let us take another example n=9
9 != 2
9%2 != 0
value of i       computation      loop count
3                      9%3 ==0             1     set flag to indicate number not prime break from loop
9 is not prime
 
We can even enhance above algorithm because there is certainly something it is checking twice
For example, we take the given number to be 11
11%2!=0 this means the given number is odd
multiplication of two odd numbers result in a odd number
odd*odd =odd (always)
even*odd=even (always)
even*even=even (always) 

Now we have to check if 11 is completely divisible by odd number series (excluding 1) less than 11. i.e { 3,5,7,9 }
if 11 is not prime then
multiplication of any two values in set {3, 4, 7, 9} should make 11.
for example
either
3*3 should be 11
or
3*5 should be 11
or
3*7 should be 11
or
3*9 should be 11
or
5*5 should be 11
or
5*7 should be 11
and so on ........
but none are
so 11 is Prime
Now we shouldn't be bothered to check for value above 3*3 because 3*3 is 9 and 3*5= 15 (we see 3*4 is 12 ) so we know 3*3 is the best we need to check if the number is prime.

lets take n= 53
we check if its 2, but  it is not.
we check if it is divisible by 2, it is not. Hence is it odd.
we check it with odd number series excluding 1
3, 5, 7, 9, 13.....
 3*3<=53 ( 53%3!= 0)
5*5<=53  ( 53%5!= 0)
7*7<=53   (53%7!= 0)
9*9>53  Stop here
we can stop here and we can say number is prime

let us take n=49
we check if its 2, but  it is not.
we check if it is divisible by 2, it is not. Hence is it odd.
we check it with odd number series excluding 1
3, 5, 7, 9, 13.....
3*3<=49 (49%3!=0)
5*5<=49  (49%5!=0)
7*7<=49  (49%7==0)
Number is not prime.

It can be seen that square root of given number can be limit of our test of whether number is prime or not.

 #include<stdio.h>
#include<math.h>
int main()
{
        int n;
        int i;
       float nsqrt;
       int flag=1;

       printf("\nEnter a number:");
       scanf("%d",&n);

       if(n==2)
              {
               printf("\n%d is Prime",n);
               return 0;
              }
         if(n%2==0)
             {
               printf("\n%d is not Prime",n);
               return 0;
             }
        else
            {
              nsqrt=sqrt(n);
              for(i=3;i<=nsqrt;i+=2)
                   {
                      if(n%i==0)
                             {
                                 printf("\n%d is not prime",n);
                                  flag=0;
                                   break;
                               }
                       }
                     if(flag==1)
                           printf("\n%d is prime",n);
               }
                return 0;
}


 

Swap using XOR gate

XOR or Exclusive-OR is a digital logic gate. Digital Logic permits only two value or states (the binary states) of 0 and 1 as inputs or outputs. A gate usually has two or more inputs and a single output

Simply stating an XOR gate give 0 output when the inputs are same(both . When the inputs are different it gives 1 as ouput.

1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 0

We can compile the result into a cleaner tabular form known as truth table.
Going with existing terminology of digital logic, we can say that 1 represent True and 0 represent False.


a   b     a XOR b
0   0           0
0   1           1
1   0           1
1   1           0

What would be 1010111 XOR 1000101
1010111
1000101
-----------
0010010 (Answer)

8 XOR 1=9?Covert both to binary equivalent and add extra zeros to left hand side if necessary
8=1000
1=0001 [zeros added to left]
---------
9=1001


XOR be used to Swap binary data in following manner
a= a XOR b
b= a XOR b
a= a XOR b

lol?

Say a= 7 and b=2
binary equivalent of 7 is 111 and of 2 is 010
a= 111 XOR 010 = 101 
b= 101 XOR 010 = 111
a= 101 XOR 111 = 010
a=2, b=7

In C Language bitwise XOR Operator is represented by ^ (exponent) sign.
so swap will be be done by
a=a^b;
b=a^b;
a=a^b;







 

Swap using addition and subtraction operation

Suppose a bus stops at a terminal. All the people in the bus want to get down and all the people standing out want to get in and there is only one exit and entry door in the bus.
In this case it would be easier for everyone in the bus to get down and then everyone standing outside to get in. At one point all the persons are standing outside bus.

The above example is similar case is similar to swap using addition and subtraction operation.
Swap
a=a+b
b=a-b
a=a-b

Say
a=5,b=3
a=5+3=8  [a=a+b]
b=8-3=5  [a=a-b]
a=8-5=3  [a=a-b]
a=3,b=5

The problem with this kind of swap is that it is applicable only to numeric data. Addition of numbers can result in a number greater than the size the variable or memory location can hold leading to overflow error.

Swap using a temporary variable

Swapping means exchanging contents of two memory location or variables. There are various application of swapping in Computers. Swapping is used in variety of Sort algorithms. On a wider perspective swapping is used to provide virtual memory.

Swap using a temporary variable is very simple.
temp=a
a=b
b=temp

Say a=4, b=7
temp=4   [temp=a]
a=7         [a=b]
b=4         [b=temp]
a=7, b=4

Swap using a temporary variable is applicable to any kind of data value.

Pythagorean Triplets

A Pythagorean Triplet is set of three positive integers (a,b,c) such that

a²+b²=c²

^{For example (3,4,5) , (5,12,13), etc.}

^{Multiplying the triplets with a same number gives another triplets}

^{for example 2*(3,4,5)=(6,8,10)}

^{Following is the program to print Pythagorean Triplets where (a,b,c)<100 and can not be multiple of each other or factorised by each other i.e. if there is a set of (3,4,5) then (6,8,10) shoulnd be part of output.}

^{#include<stdio.h>
#include<math.h>
int check(int x,int y,int z)
{
        int i=2,r1,r2,r3,r;
        while(i<=x)
               {
                   r1=x%i;
                   r2=y%i;
                   r3=z%i;
                   r=r1+r2+r3;}

                   ^{if(r==0)
                      break;
                   else
                       i++;
                }}

           <sup>if (r==0)
                return 0;
           else
                return 1;
}



int main()
{

       float t=0;
       int a=0, u=0;
       int i, j;


       for(i=3;i<100;i++)
               {
                      for(j=i+1;j<100;j++)
                            {
                                 u=i*i+j*j;</sup>

                                 ^/*

                                  ^{sqrt() belongs to math.h header file. sqrt(4)=2, sqrt(4.5)=2.12132}

                                 ^{*/
                                  t=sqrt(u);
                                  a=t;
                                   /*} 

                                   ^{ceil() belongs to math.h header file. ceil(4.6)=5}

                                   ^{floor() belongs to math.h header file. floor(4.6)=4}

                                  ^{*/
                                   if(ceil(t)==floor(t)&& check(i,j,a))
                                              printf("(%d,%d,%d)\n",i,j,a);
                             }
                   }}

           ^{return 0;
}}

Binary of a number: logic and program

Binary (Base 2) value of a number involves
1)dividing the number by 2 and storing the remainder in the array.
2)dividing the number by 2.
3)repeating the above steps until number becomes zero.
4)printing the array in reverse order.

taking number =5
index=0
number=5 (not equal to 0)
rev[index=0]=number%2=5%2=1
index=index+1=0+1=1
number=number/2=5/2=2

number=2(not equal to 0)
rev[index=1]=number%2=2%2=0
index=index+1=1+1=2
number=number/2=2/2=1

number=1 (not equal to zero)
rev[index=2]=number%2=1%2=1
index=index+1=2+1=3
number=number/2=1/2=0

number=0 (stop loop)

Print array in reverse order
for(i=index-1  ;i<=0;i--)
print a[i]
initially
i=3-1=1 a[2] is printed
i=2-1=1 a[1] is printed
i=1-1=0 a[0] is printed

#include<stdio.h>
int main()
{
           int i , index;
           unsigned long num, num_copy;
           int num_rev[20];

          /* taking size equal to 20 means it can store binary number of 20 places

             number upto 1024*1024 (2^20) can be entered by the user

            If this value is exceeded by user then there will be overflow in array

            This error will  not be reported as bound checking is not done automatically in C for arrays */

 

           printf("\nEnter a +ve number(less than 1048527:");
           scanf("%d",&num);
           num_copy=num;
         
           index=0;
           while(num_copy!=0)
           {
                       num_rev[index++]=num_copy%2;
                       num_copy=num_copy/2;
            }
           
            printf("\nBinary Equivalent of %d is ",num);
            for(i=index-1;i>=0;i--)
                  printf("%d",num_rev[i]);

return 0;
}
                      

Reversing a number logic and program

Reserving a number simply involves
1)Intially taking the remainder as 0
2)Calculating and storing remainder of a number when divided by 10.
3)Multiplying the immediate remainder by 10 and adding it to previous value of remainder.
4)Dividing the number by 10
5)Repeating the above steps until number becomes 0.

For example
taking all variables as integers so that fractional part is truncated during division
number=532 (not equal to 0)
immediate remainder=number%10=532%10=2
previous remainder= (previous remainder*10)+immediate remainder=0*10+2=2
number=number/10=532/10=53

number=53 (not equal to 0)
Repeat steps
immediate remainder=number%10=53%10=3
previous remainder=(previous remainder*10)+immediate remainder=2*10+3=23
number=number/10=53/10=5

number=5 (not equal to 0)
Repeat steps
immediate remainder=number%10=5%10=5
previous remainder=(previous remainder*10)+immediate remainder=23*10+5=235
number=number/10=5/10=0

number=0
Stop loop


#include<stdio.h>
int main()
{
        int num, num_copy, rem,rev;
        printf("\nEnter the number to be reversed:");
        scanf("%d",&num);
        num_copy=num;
        rem=0;
        rev=0;

        while(num!=0)
        {
                rem=num%10;
                rev=rev*10+rem;
                num=num/10;
         }

      printf("\nReverse of %d is %d",num_copy,rev);
      return 0;
}

Hello World

Traditionally all programming text books begin with same a common program that prints Hello World on the screen

So now lets walk through a simple procedure of writing this simple program that prints hello world on the screen in C.

Open the text editor and write the following program and save it as a file with .c extension say helloWorld.c  in CProgs folder on desktop

---------------------

 /* Program that prints Hello World on the screen */  

#include<stdio.h>

int main()

{

printf("Hello world\n");

return 0;

}

-----------------------

Compiling and running the Program

1. Open the command prompt (Start->Run->type cmd and press enter or  Start->All Programs-> accessories->Command Prompt)

2. Navigate to the directory where you stored the C program. say 

C:\Users\September31\Desktop\CProgs>

3. Write the following command to compile the  program using following command

C:\Users\September31\Desktop\CProgs> gcc helloWorld.c -o helloWorld

This will produce a helloWorld.exe file in CProgs folder

4. Now you can run the file at Command Prompt 

C:\Users\September31\Desktop\CProgs>helloworld

5. Output will be displayed.

Hello world

Going through the Programs
/* Represents multi-line comments which do not effect result and are only there to make the program more readable and understandable */

#include <stdio.h> - includes the library header file stdio.h that is for standard input and output. It is used here because we need a library function "printf".

int main() - main() function is the where the processing of a C program starts from.
usually syntax of a function in c is :
return-type function-name(type parameter1,type parameter2){ }

printf("Hello world\n");
printf(" Type text to be printed in double quotes \escape sequence");
is the syntax for printf which is a built-in library function of defined in stdio.h header file. The text to be printed is written in double quotes. Whenever backslash '\' is encountered within double quotes it means a Escape Sequence. \n does not print '\n' on screen,rather it signifies newline which moves the cursor to the beginning of next line. There are various other escape sequence or backslash characters that can be used such as \t represents tab spaces and \b represent backspace.
the printf statement is followed by a semicolon (;) which is a terminator.

return 0;
A function should always return some value if it is defined with a return type. a function with no return type is void and should be declared in following manner.
void function-name(type parameter)
A function may also not have a parameter list. It can be declared as following
void function-name(void)
or simply
void function-name()

A function in C begins with opening curly brace and end with a closing curly brace.They represent the scope of a function and tell us where a program has begun and where it has end.
They are used with decision control statements and looping statements and also with arrays , structures and have different uses and significance.

Special care should be taken in putting terminators after appropriate statements and closing all opened curly braces as these are sources of most commonly occurring errors in the program.

Basic definitions and setup

This section will cover following topics:-

1.What is programming?

2.What is a algorithm?

3.Why learn a Computer Language?

4.What skills programming require?

5.How can you start programming in C?

Skip to 5. if you already know about computer programming.

1. What is programming?

Programming simply means to tell a computer what to do and also how to do it.

2. What is algorithm?

Algorithm  is steps or methods the computer needs to be told to do something. Although there is huge difference between when you teach something to a computer or you teach something to a kid.

Many might argue that computers can accomplish wide variety of daunting tasks without error. So computer is more intelligent than a kid. But sadly it is not. It has to be told everything  (EVERYTHING). If you tell your kid to eat, he will eat, but if you want to tell a Programmable-Robot to eat you will have to tell him to eat through mouth, how to chew, how to gulp, etc, etc. Although computer has no capability to exhibit natural intelligence it successfully does whatever told. It wont tire doing long repetitive tasks all day long and night and wont even ask for salary given you have taught (programmed) it well.

3. Why learn computer language?

Computer do not understand the language of any human being (no english, spanish or french). Although  I am writing this blog, it does not mean computer understands what I write. Although a person who does not know much about computer might argue that whenever he spell a word wrong or make grammatical error computer word processors and editors indicate these flaws and suggest the correct usage. But it does not comes naturally to a computer, it has been programmed to do this.

Computer only understands language of two states or alphabets:the Binary Language of 0 and 1. In terms of electrical signal the flow of current is indicated by 1(up or high signal) and the restriction in flow of current is represented by 0(down or low signal). This language is also known as Low Level Programming Language or machine language.

But it will be tedious task to instruct a computer by remembering and writing long series of  0 or 1 for various instructions. Therefore computer programmers thought of solutions to make life simpler for themselves and other programmers through compilers and interpreters. Suppose you want to communicate to a polish guy and you don't know the polish language. You will hire a interpreter to communicate who is well versed in both english and polish. Voila! Problem sovled.

Similarly compilers and interpreters are programs which convert source code written into machine language. You write PRINT("Hello") which when converted into machine code say 1010101010 and basically prints Hello on monitor.

High level Languages consist of variables, symbols and special keywords resembling to common english words (for example print, if else) and a proper defined way of usage of keywords which are converted into machine language by compilers or interpreters. If the guidelines are not followed in usage of keywords then syntax error occurs. So, learning a High Level Language simplifies our task of  instructing a computer but we do need to remember its grammar/syntax.

4. What skills programming require?

Programming requires knowledge of programming language and algorithms. There are loads of programming languages which are suited for variety of work for example- Fortran was developed for Scientific Calculation purpose Lisp is a language designed for ease of writing AI(Artificial Intelligence) Programs. There can be million solutions to a problem but there will definitely be a "good" solution. There can be variety of parameters on which you can call a solution good. A solution can be good if it requires less resources. Resource can means less storage space, less lines in programs(less line of code), or less time to give result. Through programming one can find a solution to problem and then enhance the solution to form a better one.

5.  How can you start programming in C?

There are variety of compilers for C but i would be using GCC compiler.

If you are using Linux operating system (such as ubuntu), it already has a GCC compiler.

If you are using Windows then i would recommend  downloading MinGW.http://sourceforge.net/projects/mingw/

 A text editor will also be required for writing the code(program). One can use built-in Text Editor Notepad of Windows. But the editor is very basic. It will be more convenient to download Notepad++ http://notepad-plus-plus.org/download/v6.5.2.html 

Most developer use Linux platform native editor called "Vim" which is bit complex and requires some learning.Vim can be downloaded for Windows at  http://www.vim.org/download.php

I will be using gcc compiler and Vim Editor on Windows OS.

Setting Up MinGW

1.Download the MinGW from the address provided http://sourceforge.net/projects/mingw/

2.Extract the files to a folder say - C:\Program Files\CodeBlocks\MinGW

3.Now set the path in Environment Variables to C:\Program Files\CodeBlocks\MinGW\bin

Left click on My Computer>Properties>Advanced System Setting>Environment Variables

Click on Path under System Variables and append this to the already existing paths after adding a semicolon(;) C:\Program Files\CodeBlocks\MinGW\bin;