Construct an integer from a given set of integers using bitwise operations (and, or, not)

Question

This is a question inspired by a programming problem I've been given, so I need to implement an algorithm. Here I am not asking the complete solution, instead I'd like to get some hints about the possible approaches, or maybe some indications on which area of math / standard algorithms I should study to understand the problem.

I have a set of integers $a_1, a_2, ..., a_n$ and I need to determine whether it's possible to construct another integer $x$ by using $a_i$ and bitwise boolean operations AND, OR, NOT and construct such a formula in case it's possible.

To get away from the terminology of the Computer Science, which is also the reason why I post it on Math.SE, the question calls for many ideas from math. We can consider the integers as the elements of a powerset of the $S = \{1, \dots, 32\} $. So we are given a subset $A \subseteq \mathcal{P}(S)$ and we need to determine whether a given $x \in \mathcal{P}(S)$ belongs to the closure of $A$ under the operations of set union, set intersection and set complement relative to $\mathcal{P}(S)$ or not.

I also think there could be similar representations in terms of boolean algebra and boolean vectors (operations on each component behave like boolean multiplication, addition and negation).

I have an intuition that some of those approaches could help in determining whether there is a solution or not, but I don't know whether one of the could produce a formula, and in this case maybe some algorithmic idea should work provided that there are not so many integers given on input.

Answer 1

Let's fill out each $a_i$ number with $0$'s in the front, so all of them have the same length.

So we have the following bit-vectors (for example):

$$a_1 = 01101001 \\ a_2 = 11100011 \\ a_3 = 00010110 \\ \vdots$$

So the question is: "Can we create each number from $00000000$ to $11111111$ using only $\lor,\land,\lnot$ from these numbers, for example $a_{new}= \lnot a_1 \lor (a_2 \land \lnot a_3) \land \dots$?"

The answer is, well... sometimes. But for that I need to define the field we are working in and precisely what the above notations ($\lor, \land, \lnot$) mean in that field.

---

Definition: Let $\Bbb{F}_n$ be a field such that it contains all $n$-long bit-representaions for the numbers $\{0,1,\dots,2^n\}$, and I'll define three bitwise operations on it:

$\forall a_1 = (a_1^1 a_1^2 \dots a_1^n)_2 \in \Bbb{F}_n \text{ and} \\ \forall a_2 = (a_2^1 a_2^2 \dots a_2^n) _2\in \Bbb{F}_n$

(where $a = (a^1 a^2 \dots a^n)_2$ is the binary representation of $a$):

• $a_1 \lor a_2 = (b^1 b^2 \dots b^n | \forall i \in \{1,\dots,n\}: b^i = 1 \iff a_1^i = 1 \text{ or } a_2^i = 1)$
• $a_1 \land a_2 = (b^1 b^2 \dots b^n | \forall i \in \{1,\dots,n\}: b^i = 1 \iff a_1^i = 1 \text{ and } a_2^i = 1)$
• $\lnot a_1 = (b^1 b^2 \dots b^n | \forall i \in \{1,\dots,n\}: b^i = 1 \iff a_1^i = 0)$

---

We could prove that $(\Bbb{F},\lor,\land,\lnot)$ is a well-defined vector field, so the following method will work:

• If we find a basis that can generate all elements of $\Bbb{F}$, we are done.
• The standard basis is exactly the same as for $\Bbb{R}^n$: $\ e_1 = (100\dots 0), e_2 = (010\dots 0), \dots, e_n = (000\dots 1).$

Since if we can generate $e_1, e_2, \dots, e_n$, we can generate anything with $\lor$'s, for example:

$$a = (11001) = (10000)\lor (01000) \lor (00001).$$

Now the question is: Are the given $a_1,a_2,\dots,a_n$ bitvectors transformable to $e_1,e_2,\dots,e_n$?

• Since this is a well-defined vector space, we can use a modified Gauss-Jordan elimination to find if the matrix $A := \begin{bmatrix} a_1 & a_2 & \dots & a_n \end{bmatrix}^T$ is row-reducable.
• In other words, the solution will depend on the $rank(A).$

---

Modified Gauss-Jordan elimination for $\Bbb{F}_n$:

A matrix $A$ is given, which we want to transform into $I_n = \begin{bmatrix} e_1 & e_2 & \dots & e_n \end{bmatrix}^T$, using the following steps a finite number of times:

• $(1)$ Swap two rows with each other.
• $(2)$ Take the $\lnot$ of a row.
• $(3)$ Transform a row $r_i$ to $r_i \land r_j$ where $r_j$ is any other row in the matrix.

Note, that $\lor$ could potentially lessen the rank of the matrix. However, all the previously mentioned steps preserve the rank of the matrix.

I have also found, that instead of steps $(2)$ and $(3)$ it's usually easier to

• $(2 + 3):$ Transform a row $r_i$ to $r_i \land \lnot r_j$ where $r_j$ is any other row in the matrix.

Because this is actually very similar to the actual Gauss-Jordan elimination's reduction step, where you transform a given value (or values) in the matrix to $0$.

---

Example:

$$a_1 = (101) \\ a_2 = (110) \\ a_3 = (011)$$

I'll use steps $(1)$ and $(2 + 3)$ to transform it into the $I_n$ matrix:

$$\begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \stackrel{r_2 \rightarrow r_2 \land \lnot r_1}{\longrightarrow} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \stackrel{r_3 \rightarrow r_3 \land \lnot r_2}{\longrightarrow} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \stackrel{r_1 \rightarrow r_1 \land \lnot r_3}{\longrightarrow} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

So in this case, all $3$-long vectors could be generated.

---

Other theorems could also be proven for $\Bbb{F}_n$:

• When given a set of $a_1, \dots, a_k$ $n$-long vectors and $k < n$, then $rank(A) \le k < n$, meaning that for sure, not all $n$-long vectors can be generated.
• When given a set of $a_1, \dots, a_n$ $n$-long vectors and they're linearly independent for $\land$ and $\lnot$, (they can't be expressed from each other using only $\land$ or $\lnot$ and no brackets, so $a_i \ne (\lnot)a_1 \land (\lnot)a_2 \land \dots$), then the resulting matrix $A$ will have a $rank(A) = n$, and every $n$-long vector can be generated from them.

---

Okay, so what can be generated from the $a_1,\dots,a_n$ vectors if the above matrix has $rank(A) < n$? In other words, what is $span(a_1,\dots,a_n) = ?$

After doing the entire Gauss-Jordan row-reduction, some columns will be entirely $0$. The digits corresponding to those rows will depend on other columns, depending on the linear correspondance between $a_1,\dots,a_n$.

For example,

$$a_1 = (1101100) \\ a_2 = (0111100)$$

The resulting matrix will be

$$\begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 \end{bmatrix} \stackrel{\dots}{\rightarrow} \begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix}$$

So only the $3$rd digit will be significantly modifyable, and if we choose a digit from $\{1,2,4,5\}$, the chosen digit will determine all the others from the set, and the ones outside of the set will be opposite of the determined ones.

Unfortunately each case is different, and it's not obvious how this $span(a_1,\dots,a_n)$ subspace will look in general, unless of course $rank(A) = n$, in which case it's the entire bitspace, $\Bbb{F}_n$.

---

Summary:

• The answer to your question is: All $n$-long numbers can be gotten, if and only if there are at least as many $a_i$ numbers as their length $(n)$, and the above $A := \begin{bmatrix} a_1 & a_2 & \dots & a_{n+k} \end{bmatrix}^T$ is row-reducable to $[I_n|B_{n \times k}]^T$, where $B_{n \times k}$ is some $n \times k$ bitmatrix (using the $(1)$ and $(2 + 3)$ steps above).
• Most linear algebra theorems apply, we just have to be careful how we handle the Gauss-Jordan elimination and addition via $\land, \lor$ and $\lnot$.