Sum of bitwise AND of all possible subsets of given set

https://www.geeksforgeeks.org/sum-bitwise-possible-subsets-given-set/

Given an array, we need to calculate the Sum of Bit-wise AND of all possible subsets of given array.

Examples:

Input : 1 2 3
Output : 9
For [1, 2, 3], all possible subsets are {1}, 
{2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Bitwise AND of these subsets are, 1 + 2 + 
3 + 0 + 1 + 2 + 0 = 9.
So, the answer would be 9.

Naive Approach, we can produce all subset using Power Set then calculate Bit-wise AND sum of all subset.

A Better approach, we are trying to calculate which array element is responsible in producing the sum into subset.
Let’s start with the least significant bit. To remove the contribution from other bits, we calculate number AND bit for all numbers in the set. Any subset of this that contain a 0 will not give any contribution. All nonempty subset that only consist of 1’s will give 1 in contribution. In total there will be 2^n – 1 such subset each giving 1 in contribution. Same goes for the the other bit. We get [0, 2, 2], 3 subset each giving 2. Total 3*1 + 3*2 = 9

Array = {1, 2, 3}
Binary representation
positions       2 1 0    
        1       0 0 1
        2       0 1 0
        3       0 1 1
              [ 0 2 2 ]
Count set bit for each position
[ 0 3 3 ] subset produced by each 
position 2^n -1 i.e. n is total sum 
for each position [ 0, 3*2^1, 3*2^0 ] 
Now calculate the sum by multiplying 
the position value i.e 2^0, 2^1 ... . 
 0 + 6 + 3 = 9

    static final int BITS = 32;

      

    static int andSum(int arr[], int n)

    {

        int ans = 0;

      

        // assuming representation of each

        // element is in 32 bit

        for (int i = 0; i < BITS; i++) {

            int countSetBits = 0;

      

            // iterating array element

            for (int j = 0; j < n; j++) {

      

                // Counting the set bit of

                // array in ith position

                if ((arr[j] & (1 << i)) != 0)

                    countSetBits++;

            }

      

            // counting subset which produce

            // sum when particular bit 

            // position is set.

            int subset = (1 << countSetBits) - 1;

      

            // multiplying every position 

            // subset with 2^i to count the

            // sum.

            subset = (subset * (1 << i));

      

            ans += subset;

        }

      

        return ans;

    }