How to express $(\lor,\land)$ multiplication in terms of $(+,\land)$ and $(\oplus,\land)$ multiplication?

110 Views Asked by At

The product of two numbers $a$ and $b$ represented in binary as $a=a_{n-1}\ldots a_1a_0$, $b=b_{m-1}\ldots b_1b_0$ is given by

$$a\times b=\sum_{i,j}\>(a_i\land b_j)\ll(i+j)$$

where $x\ll i=x\times 2^i$ is the left-shift operator. Let's call this $(+,\land)$ multiplication. Modern computers generally provide machine instructions to implement this operation. They might also provide the $(\oplus,\land)$ multiplication

$$a\otimes b=\bigoplus_{i,j}\>(a_i\land b_j)\ll(i+j)$$

often called carry-less multiplication (where $\bigoplus$ is bitwise exclusive or).

For an algorithmic problem, I'm interested in the related $(\lor, \land)$ multiplication

$$a\mathbin{\check\times}b=\bigvee_{i,j}\>(a_i\land b_j)\ll(i+j)$$

where $\bigvee$ denotes bitwise inclusive or.

Can this operation be expressed in terms of the usual bitwise and arithmetic operation including $a\times b$ and $a\otimes b$? I'm especially interested in ways that lend themselves to efficient computation.