Let $$$b = \text{bitmask}$$$.

We need to show that for any submask $$$i$$$ of $$$b$$$, the value $$$(i - 1)\ \&\ b$$$ is the largest submask of $$$b$$$ less than $$$i$$$.

Consider the integer $$$i$$$ in binary and find the last $$$1$$$-bit:

$$$i = \dots1000$$$.

Now, we know that

$$$i-1 = \dots0111$$$

and nothing inside the $$$\dots$$$ is different.

Because $$$i$$$ was a submask of $$$b$$$ and no bits higher than the lowest $$$1$$$ changed, they will also not change when performing the bitwise and $$$(i - 1)\ \&\ b$$$. The bitwise and will remove all $$$1$$$-bits from the ones at the end which are not in $$$b$$$.

This means that if $$$b$$$ looked like

$$$b = \dots1101$$$,

$$$(i - 1)\ \&\ b = \dots0101$$$.

Since we applied the bitwise and operation with $$$b$$$, the result is most definitely a submask of $$$b$$$.

Now, consider any integer $$$j$$$ strictly between $$$i$$$ and $$$(i - 1)\ \&\ b$$$. Any such integer between these must have all the same higher bits than the lowest $$$1$$$-bit in $$$i$$$ as $$$i$$$ and $$$(i - 1)\ \&\ b$$$. We know that $$$j > (i - 1)\ \&\ b$$$ and thus, $$$j$$$ must have a $$$1$$$-bit that is not in $$$(i - 1)\ \&\ b$$$. But this bit would have to be one of the last zeros that were made zeros because they weren't in $$$b$$$. This means that that integer $$$j$$$ wouldn't be a submask of $$$b$$$. Thus, there are no submasks of $$$b$$$ strictly between $$$i$$$ and $$$(i - 1)\ \&\ b$$$. $$$\square$$$

Let $$$b = \text{bitmask}$$$.

First, we are iterating over all $$$b$$$ in range $$$[0, 2^n - 1]$$$.

For each $$$b$$$, we are iterating over all of $$$b$$$.

If some integer $$$b$$$ has $$$k$$$ $$$1$$$-bits, it has $$$2^k$$$ submasks. Thus, iterating over its submasks takes $$$O(2^k)$$$ time.

For each integer $$$0 \le k \le n$$$, there are exactly $$$\displaystyle\binom{n}{k}$$$ values $$$b$$$ with $$$k$$$ $$$1$$$-bits.

Thus, the total number of iterations is $$$\displaystyle\sum_{k=0}^n 2^k\binom{n}{k}$$$.

Let $$$\displaystyle f(n, k) = 2^k\binom{n}{k}$$$.

$$$f(n, k)$$$

$$$\displaystyle f(n, k) = 2^k\binom{n}{k}$$$

$$$\displaystyle f(n, k) = 2^k\left(\binom{n-1}{k-1} + \binom{n-1}{k}\right)$$$

$$$\displaystyle f(n, k) = 2^k\binom{n-1}{k-1} + 2^k\binom{n-1}{k}$$$

$$$\displaystyle f(n, k) = 2 \cdot 2^{k-1}\binom{n-1}{k-1} + 2^k\binom{n-1}{k}$$$

$$$\displaystyle f(n, k) = 2f(n-1, k-1) + f(n-1, k)$$$

We need to show that $$$\displaystyle\sum_{k=0}^n 2^k\binom{n}{k} = \sum_{k=0}^n f(n,k) = 3^n$$$. $$$(*)$$$

Consider a proof by induction:

Base case $$$n = 0$$$:

$$$\displaystyle\sum_{k=0}^0 f(0, k) = 2^0 \cdot \binom{0}{0} = 1 \cdot 1 = 3^0 = 3^n$$$

which concludes the base case.

Suppose $$$(*)$$$ is true for $$$n = m$$$. Consider the case $$$n = m+1$$$:

$$$\displaystyle\sum_{k=0}^{m+1} f(m+1,k)$$$

$$$= \displaystyle\sum_{k=0}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m+1} f(m,k)$$$

$$$= 2f(m,-1) + f(m, m+1) + \displaystyle\sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$

$$$\displaystyle = 2\cdot 2^{-1}\binom{m}{-1} + 2^{m+1}\binom{m}{m+1} + \sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$

If $$$b < 0$$$ or $$$b > a$$$, $$$\displaystyle\binom{a}{b} = 0$$$:

$$$\displaystyle = 0 + 0 + \sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$

$$$\displaystyle = 2\sum_{k=1}^{m+1} f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$

Re-indexing the first sum:

$$$\displaystyle = 2\sum_{k=0}^{m} f(m,k) + \sum_{k=0}^{m} f(m,k)$$$

$$$\displaystyle = 3\sum_{k=0}^{m} f(m,k) = 3 \cdot 3^{m} = 3^{m+1}$$$

which concludes the induction step. $$$\square$$$