Using bits manipulation to find sum of each subset in C++

By MRINAL SINHA

The project uses the bits manipulation technique to find the sum of each subset of the given set in C++.

BIT MANIPULATION :

All data in computer programs are internally stored as bits, i.e., as numbers 0 and 1.

In bits manipulation, we represent integers as bits and manipulate them using bit operations. There are many uses for bit operations in algorithm programming.

BIT OPERATION : 

AND operation : 

For example, 22 & 26 = 18,
   10111 (23)
& 11010 (26)
= 10010 (18)

OR operation : 

For example, 22 | 26 = 30,
   10111 (23)
 | 11010 (26)
= 11111 (31)

XOR operation :

For example, 22 ^ 26 = 12,
   10111 (23)
^ 11010 (26)
= 01101 (13)

NOT operation :

  x = 00000000000000100000010000011101
~x = 11111111111111011111101111100010

ALGORITHM :

1. We will run the outer loop for the value of j=0 to j= power(2,n)-1, and one inner loop run for the value of i=0 to i=n-1.

2. We will check if the ith bit if the integer j is set or not.

3. If the ith bit is set then add A[i] to the sum.   

4. Return sum.

REQUIREMENT :

1. Little knowledge in bits manipulation and knowledge of programming language c++.

2. Any IDE to compile and run the code.

NOTES :

1. 1 << n is equal to pow(2,n).

2. j&(1<<i) is used to find that ith bit of integer j is set or not.