In this file you will find all information about bit manipulation.

Bit_manipulation.c

/*
    Author : Rohit Singh
    Purpose: TO implement all bit manipulation.
/*

/*
########################################## BIT MANIPULATION ##########################################
______________________________________________________________________________________________________

Bit wise operators are : -

~  = NOT 								( if bit = 1 then becomes 0 and vice versa )
|  = OR  								( if both bit are 0 then becomes 0 else 1 )
&  = AND 								( if both bit are 1 then becomes 1 else 0 )
^  = XOR ( x ^ x ) = 0, ( 0 ^ x ) = x   ( if both bits are different then 1 else 0 )
>> = RIGHT SHIFT ( x >> 1 ) = x / 2
<< = LEFT SHIFT  ( x << 1 ) = x * 2

Binary addition : -
---------------
         1     1
Ex : -     1 1 0 1
       +   1 0 0 1
         _________
         1 0 1 1 0    ( It simply works on sum and carry )

Binary subtraction : -
------------------
Ex : -
        1 0 1 0    ( here we substarct 1 from 10 which results 9 )
                   ( In binary subraction first we do 2's complemet of first value then add it to the first value to find out subtraction )
    -	  0 0 0 1    ( i.e [a - b] = [a + (~b + 1 )] )
        _______    ( 2's complement of some value is the -ve part of the same value )
        1 0 0 1


Odd and Even : -
------------
1 & n == 0 if n is even else n is odd

:--- Last bit of even number is 0 and for odd number it is 1
     So we that 1 & 0 = 0 and 1 & 1 = 1


Swap two numbers : -
----------------

Suppose a and b are the two number which we want to swap then

        a = a ^ b
        b = a ^ b
        a = a ^ b

    That's it it will swap a and b value


########################################## BIT MASKING ##########################################
_________________________________________________________________________________________________


Find ith bit : -
------------
Formula = ( n & mask ) == non zero then 1 else 0 is present at that position

        Here we derived MASK
    ->  if you want to find bit of kth bit then, mask = ( 1 << k )

By this we can find any bit inside of a number at any position.

Ex : -
        1 0 1 0 1 1 0 1          ( mask for 5 th bit is 0 0 0 1 0 0 0 0)
    &	  0 0 0 1 0 0 0 0
    --------------------
        0 0 0 0 0 0 0 0    = zero so at 5 th position 0 is placed


Set ith bit ( making bit == 1 ): -
-------------------------------
Formula ==> new_value =  ( value | mask )

        Here we derived MASK
    ->  if you want to find bit of kth bit then, mask = ( 1 << k )

By this we can set any bit inside of a number i.e making bit = 1.

Ex : -
        1 0 1 0 1 1 0 1          ( mask for 5 th bit is 0 0 0 1 0 0 0 0)
    |	  0 0 0 1 0 0 0 0
    --------------------
        1 0 1 1 1 1 0 1     <-- Here 5 th bit becomes 1


Clear ith bit ( making bit == 0 ) : -
---------------------------------
Formula ==> new_value =  ( value ^ mask )

        Here we derived MASK
    ->  if you want to find bit of kth bit then, mask = ~ ( 1 << k )

By this we can clear any bit inside of a number i.e making bit = 0.

Ex : -
        1 0 1 1 1 1 0 1          ( mask for 5 th bit is 1 1 1 0 1 1 1 1 )
      ^	1 1 1 0 1 1 1 1
    --------------------
        1 0 1 0 1 1 0 1      <-- Here 5 th bit becomes 0
*/

/*
############################################ SOME EXAMPLES ############################################
_______________________________________________________________________________________________________

1) How many digits are present in some decimal value.
Answer : - number_of_digits = (int)(log10(digit)) + 1

2) How many binary bits are present in some decimal value.
Answer : - number_of_binary_bits = (int)(log2(digit)) + 1

3) How many 1's' are present in binary value of some decimal value.
Answer : -
*/
        #include<stdio.h>

        int main()
        {
            int n = 5;
            int count = 0;
            while(n)
            {
                count++;
                n &= (n-1);
            }
            printf("Count = %d",count);
            return 0;
        }

/*
Expalnation : -
_________________

n & ( n - 1 ) will remove least significant bit i.e 1 1 0 1 -> 1 1 0 0 -> 1 0 0 0 -> 0 0 0 0
n & ( n - 1 ) operation will give 0 if n is in power of 2

Altenative method :
*/
        #include<stdio.h>

        int main()
        {
            int n = 5;
            int count = 0;
            while(n != 0)
            {
                if(n & 1)
                    count++;
                n >>= 1;
            }
            printf("Count = %d",count);
            return 0;
        }

/*
4) Find the min number of bit required to convert a into b.
*/
        #include<stdio.h>

        int main()
        {
            int a,b;
            printf("Enter A and B : ");
            scanf("%d %d",&a,&b);
            // here mismatch bit will become 1 so we just have to count 1
            int bit_count = a ^ b;
            // here we count total number of 1's in bit_count.
            int count = 0;
            while(bit_count != 0)
            {
                if(bit_count & 1)
                    count++;
                bit_count >>= 1;
            }
            printf("Count = %d",count);
            return 0;
        }

*/