Q:

What is the efficient way of calculating sum of Bitwise AND of all subsets of an array in Java?

For [1, 2, 3], all possible subsets are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
The sum of AND of these subsets are, 1 + 2 + 3 + 0 + 1 + 2 + 0 = 9.
this is what i have tried:
public class Main
{
static void printSubsets(int set[])
{
    int n = set.length;
    int total=0;

    for (int i = 0; i < (1<<n); i++)
    {
        int sum=1;

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

            if ((i & (1 << j)) > 0)

                sum = sum & set[j];

                total= total+sum;

    }
    System.out.print(total);
}

public static void main(String[] args)
{
    int set[] = {1, 2, 3};
    printSubsets(set);
}
}

but its not giving correct output

A:

You may sum up the contribution for each bit.
Lets start with the least significant bit. To remove the contribution from other bits, we calculate number AND bit for all numbers in the set. For your example the result will be [1,0,1]. 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
static void printSubsets(int[] set) {

    long total = 0;

    for (int bit=1; bit!=0; bit<<=1) {

        int numbersWithBitSet = 0;
        for (int i : set) {
            if ((i&bit)!=0) numbersWithBitSet++;
        }

        long subsets = (1L<<numbersWithBitSet)-1;
        total += bit * subsets;
    }

    System.out.println("Result: " + total);
}

