Complexity of bitwise AND operation on bit string regular expressions
Formalism

Let me formalize your problem as follow.  Define a gegular expression as an expression that follows the following grammar:

$$E ::= 0 | 1 | E_1 E_2 | E^k,$$

where $k$ ranges over positive integers and $E_1,E_2$ range over gegular expressions.  Note that these are not regular expressions, as Yuval Filmus explains, even though they are related.

Obviously, each gegular expression codes for a single binary string.  If $E$ is a gegular expression, let $[E]$ be the binary string is codes for.  Also let $\text{len}(E)=\text{len}([E])$ denote the length of the binary string $[E]$.  Of course, these can be easily computed recursively: e.g., $\text{len}(E_1 E_2) = \text{len}(E_1) + \text{len}(E_2)$ and $\text{len}(E^k) = k \times \text{len}(E)$.

Given two gegular expressions $E_1,E_2$, the ultimate goal is to find a third gegular expression $E_3$ such that

$$[E_3] = [E_1] \land [E_2],$$

i.e., that represents the bitwise-AND of the bit strings that $E_1,E_2$ code for.  If this holds, we will write $E_3 = E_1 \land E_2$.  ($E_3$ may not be unique -- there may be multiple acceptable $E_3$ -- but we won't let this bother us.)

Helpful tools

Here are some little lemmas that are helpful.

First, if $E$ is a gegular expression and $\ell$ is a positive integer, we can compute a new gegular expression that codes for the first $\ell$ bits of $[E]$.  Define $\text{prefix}_\ell(E)$ to be this gegular expression.  We can compute $\text{prefix}_\ell(E)$ recursively using the following relations:

$$\text{prefix}_\ell(E_1 E_2) =
\begin{cases}
\text{prefix}_\ell(E_1) &amp;\text{if $\ell &lt; \text{len}(E_1)$}\\
E_1 &amp;\text{if $\ell = \text{len}(E_1)$}\\
E_1 \; \text{prefix}_{\ell-\text{len}(E_1)}(E_2) &amp;\text{otherwise.}
\end{cases}$$

$$\text{prefix}_\ell(E^k) = E^{\lfloor \ell / \text{len}(E) \rfloor} \; \text{prefix}_{\ell \bmod \text{len}(E)}(E).$$

You might notice that this does not increase the size of the gegular expression too much (at most a quadratic blowup, and usually much less).

Also, there are some special cases where your problem is easy.  For instance.

$$E_1^k \land E_2^k = (E_1 \land E_2)^k$$

if $\text{len}(E_1)=\text{len}(E_2)$.

If the exponents are not identical, we can reduce to the above case.  Let $E_1,E_2$ be two gegular expressions of lengths $\ell_1,\ell_2$, respectively (i.e., $\ell_i = \text{len}(E_i)$).  Let $m = \text{lcm}(\ell_1,\ell_2)$ be the least common multiple of their lengths.  Then

$$E^k = (E E \cdots E)^{\lfloor k/m \rfloor} E E \cdots E$$

holds for all $E,k,m$, where the first $E E \cdots E$ represents $m$ concatenations of $E$ and the second $E E \cdots E$ represents $k \bmod m$ concatenations.  Thus we have

$$E_1^{k_1} \land E_2^{k_2} =
(E_1 E_1 \cdots E_1 \land E_2 E_2 \cdots E_2)^{k_3} \;
\big( \text{prefix}_{\ell'_1}(E_1^{k_1}) \land \text{prefix}_{\ell'_2}(E_2^{k_2}) \big),$$

Also, if $\text{len}(E_1) = \text{len}(E'_1)$, then

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land E'_1) (E_2 \land E'_2).$$

If they are not of the same length, say $E_1,E'_1$ have lengths $\ell_1,\ell_2$ where $\ell_1&lt;\ell_2$, then we can express their bitwise-AND as

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land \text{prefix}_{\ell_1}(E'_1)) (\text{prefix}_{\ell_2-\ell_1}(E_2) \land \text{tail}_{\ell_2-\ell_1}(E'_1)) (\text{tail}_{\text{len}(E'_2)}(E_2) \land E'_2).$$

(Here $\text{tail}()$ is defined analogously to $\text{prefix}()$, except it relates to the end of a string rather than the beginning.)

I think from these special cases, you should be able to build a recursive algorithm that computes the bitwise-AND of any two gegular expressions.