inclusion-exclusion principle working

Question

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$.

How many groups exists such that

$$a_{i_1}\mathbin{\&} a_{i_2}\mathbin{\&}\ldots\mathbin{\&} a_{i_k} = 0\;,$$

where $1\le k\le n$.

Operation $x\mathbin{\&} y$ denotes bitwise AND operation of two numbers.

Approach:

Use inclusion-exclusion principle in this problem.

Let $f(x)$ be the count of numbers $i$ where $A_i\mathbin{\&}x = x$.

Let $g(x)$ be the number of $1$s in the binary respresentation of $x$. Then the answer is equal to

$$(-1)^{g(x)}\cdot 2^{f(x)}$$

But I could not understand the correctness and working intuition of this.

For calculating f(x) if Number are in range 0 to 10^6 so bit required to represent them is 20.

 for(int i=0;i<20;i++) {
            for(int j=0;j<(1<<20);j++) {
                if(0 == (j & (1<<i))) {
                    f[j | (1<<i)] += f[j];
                }
            }
        }

Please Help.

For Example:

0 1 2 3

Ans: 10

Answer 1

As noted in the comments, a summation sign is missing.

There are $20$ conditions to fulfil, corresponding to each of the $20$ bits being $0$, and we're looking for the groups that fulfil all of these conditions. The number $x$ represents a subset of the conditions that are violated, namely the subset corresponding to the bits set in $x$. To form a bitwise AND result that violates the conditions represented by $x$, we can AND any number of elements $a_i$ that satisfy $a\operatorname{\&}x=x$, since then and only then will the bits in $x$ be set in the result. There are $2^{f(x)}$ groups of such elements. Thus, by inclusion–exclusion there are

$$ \sum_x(-1)^{g(x)}\cdot2^{f(x)}\;, $$

admissible groups, where $x$ runs over all natural numbers with up to $20$ bits.