To find whether a number is in power of 2 using complement and gate (very short)

A number occurring in power of has a specialty when written in its binary representation:

1     = 0000 0001

2     = 0000 0010

4     = 0000 0100

8     = 0000 1000

16   = 0001 0000

32   = 0010 0000

64   = 0100 0000

128 = 1000 0000

What happens when I subtract one from these above numbers

1-1=0          0000 0000
2-1=1          0000 0001
4-1=3          0000 0011
8-1=7          0000 0111
16-1=15      0000 1111
32-1=31      0001 1111
64-1=63      0011 1111
128-1=127   0111 1111

Before moving further we will look at Complement Operator(~) in C.
Complement of a binary number changes all 1 bits to 0 and all zero bits to 1

~(1011 0110) = 0100 1001

It is similar to XOR toggling all bits
          1011 0110
XOR    1111 1111
------------------------
           0100 1001

Never mind!

Looking at numbers in power of two and their subtraction by 1, we can establish a pattern

For example, let us take 16
 16 =  0001 0000
 ~(16) = ~(0001 0000) = 1110 1111
16-1=15 = 0000 1111

If we AND  ~16 and (16-1), it equals (16-1)

~(16) =         1110 1111
16-1=15=      0000 1111
----------------------------------
 16-1=15=      0000 1111

Hence the method to find whether the number is power of two or not.

#include<stdio.h>
int main()
{
    int num;
    printf("\nEnter number:");
    scanf("%d",&num);
    if(((num-1)&(~num))==(num-1))
        printf("%d is in power of 2",num);
    else
        printf("%d is not in power of 2",num);

    return 0;
}

Although, this short method does not tell us which power of 2 is the number like previous methods discussed. You can verify this method for numbers that are not in power of two.

To find whether a number is in power of 2 by counting number of 1 bits

2⁰=1 (or 2^0=1) Read as 2 raised to power 0

2¹=2 (or 2^1=2) Read as 2 raised to power 1

2²=4 (2*2=4)

2³=8 (2*2*2=8)

2⁴=16

2⁵=32

As previously explained, 32 is 2 raise to power 5 and 22 does not come in power of 2.

So is there anything special in these number. 

Yes, there binary representation is intuitively special.

1     = 0000 0001

2     = 0000 0010

4     = 0000 0100

8     = 0000 1000

16   = 0001 0000

32   = 0010 0000

64   = 0100 0000

128 = 1000 0000

Any number which exist in power of 2 has only single 1 in its representation.

So, we can convert a number to binary and if it has only a single 1, it is in power of 2.And write a program that does not use pow() function of math.h header file

 The conversion to binary form is already explained in earlier blog

#include<stdio.h>
int main()
{
    int num, num_copy, rem, count,power;
        printf("\nEnter number:");
        scanf("%d",&num);

    num_copy=num;
    count=0;
        power=-1;

        while(num>0)
        {
        rem=num%2;

        if(rem==1)
            count++;

        num=num/2;
        power++;
    }

        if(count==1)
        printf("%d is 2 raised to %d" ,num_copy,power);
    else
        printf("number not in power of 2");


    return 0;

}

      

        

        

To find whether a number is in power of 2 using pow()

A number is in power of 2, when 2 raised to some power is equal to that number.

Is 32 in power of 2? yes
2 raised to power 5 equals 32.

Is 256 in power of 2? yes
2 raised to power 8 equal 256

Is 24 in power of 2? no

In C, header file math.h provide us pow() function
pow(x,y) -- signifies x raised to power y

So we can easily check if number is in power of two
Steps
1.Enter number
2.Set flag=0
3.Set check=0
4.Set i=0
5.loop until check < number
   1.check = pow(2,i) [ 2^i]
   2. if check equals number then Set flag equal to 1 and break from loop goto step 6
   3. increment i = i+1
6.if flag equals to 1 then number is 2 raised to power i
   else it is not.

For example
number=4
flag=check=i=0

check< 4 [ 0<4  yes. Go inside loop]
check = pow(2,0) [2^0=1]
check == number [no]
i=i+1 [0+1=1]

check< 4 [ 1<4  yes Go inside loop]
check = pow(2,1) [2^1=2]
check == number [no]
i=i+1 [1+1=2]

check< 4 [ 2<4  yes Go inside loop]
check = pow(2,2) [2^2=4]
check == number [yes] set flag=1, break from loop-goto step 6

is flag == 1 [yes]
print(number is 2 raised to power 2( value of i=2 when we break from loop)


#include<stdio.h>
#include<math.h>

int main()
{

    int i, num,check, flag;
    printf("\nEnter number:");
    scanf("%d",&num);

    i=0;
    check=0;
    flag=0;

    while(check<num)
    {
        check=pow(2,i);
        if(check==num)
        {
            flag++;
            break;
        }
        i++;
    }
    if(flag==1)
        printf("%d is 2 raised to power %d",num,i);
    else
        printf("Number is not in power of 2 ");

    return 0;
}

Toggle a bit.

Toggling a bit will mean changing a bit to 0 if it was originally 1 or changing a bit to 1 it was originally 0.

Suppose you have been given a bit pattern and you want to toggle all the bit in the pattern. How can you achieve it.

Simple XOR it with 1's equal to number of bits given

For example, toggle (1101 0101 01)--> 0010 1010 10

           1101 0101 01
XOR     1111 1111  11   
---------------------------
           0010 1010 10

Toggling the Nth bit of a bit pattern can be achieved by left shifting 1  (N-1) times and XORing it with the bit pattern

For example, change the toogle the 4th bit (from left) in 1010 1000
N=4
N-1=3

i=(1<<3);
1010 1000 XOR i

1= 0000 0001
i=1<<4 = 0000 1000

          1010 1000
XOR    0000 1000
-----------------------
           1010 0000

Simply
get n;
after_toggle = given_bit_pattern ^ (1<<(n-1));

Factorial

Factorial of a number 'n', denoted by n!, is the product of non negative number less than or equal to the given number 'n'.
n! = n*(n-1)!
n! = n*(n-1)*(n-2)*.....*(n-n)!
n! = n*(n-1)*(n-2)*.....*(0!)
n! = 0?
Nop
0! = 1
n! = n*(n-1)*(n-2)*....*(n-(n-1))*1
n! = n*(n-1)*(n-2)*.....*1*1
For example n=5
5! = 5 * 4 * 3 * 2 * 1* 0! 
5! = 5 * 4 * 3 * 2* 1 * 1
5! = 120


#include<stdio.h>
int main()
{

    int f, i, n ;

    printf("\nFactorial");
    printf("\nEnter the number(>=0):");
    scanf("%d",&n);

    if(n<0)
    {
        printf("Input not suitable");
        return -1;
    }

    f=1;
    for(i=2;i<=n;i++)
        f*=i;

    printf("%d! is %d",n,f);
    return 0;
}

Fibonacci Series

Fibonacci series is a series where f(n-1), f(n),f(n+1) are three terms in fibonacci series, then
f(n+1)=f(n-1)+f(n)
Each terms in fibonacci series is sum of previous two terms taking f(1)=1 and f(2)=1
The Series generated is as follow
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...............

Suppose we want to print fibonacci series upto  'n' numbers.
We know two intial terms of the series which are f(1)=1 and f(2)=1. Print these on the screen. take count =0 which will make the program loop till it is equal to 'n-2'. [first two terms are printed outside loop. So number of terms entered is subtracted by 2. n=n-2]
a=1, b=1 ,c=0,count=0
print(a)
print(b)
repeat until count is less than  'n-2'
 1. c = a + b
 2. print (c)
 3.  a = b    
 4.  b = c     
 5. count = count +1


for example n=5
a=1,b=1
n=n-2
count=0
print(a), print(b)

count<3 [0<3   yes]
c = a + b [a = 1, b =1,c = 1 + 1 = 2]
print (c)  [ prints 2]
a = b  [a=1]
b = c  [b=2]
count = count+1 [count = 0 + 1 =1]

count<3 [1<3 yes]
c = a + b [a = 1, b =2,c = 1 + 2 = 3]
print (c)   [ prints 3]
a = b  [a=2]
b = c  [b=3]
count = count+1 [count = 1 + 1 = 2]

count<3 [2<3 yes]
c = a + b [a = 2, b =3,c = 2 + 3 = 5]
print (c)   [ prints 5]
a = b  [a=3]
b = c  [b=5]
count = count+1 [count = 2 + 1 =3]

count<3 [ 3<3 No. Loop stops]

for n= 5, series containing 5 terms is printed
1 1 2 3 5

#include<stdio.h>
int main()
{
    int a, b, c, n, count;
    printf("\nFibonacci Series");
    printf("\nEnter number of terms(number>2):");
    scanf("%d",&n);

    a=1;
    b=1;
    printf("%d %d ",a,b);
        count=0;
    n=n-2;

    while(count<n)
    {
        c=a+b;
        printf("%d ",c);
        a=b;
        b=c;
        count++;
    }
    return 0;
}

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;
}