Is it possible to solve equations of bit wise operators?

Question

We can easily find:

a=7
b=8
c=a|b

Then c comes out to be: 15

Now can we find a if c is given?

For example:

b=8
c=15
c=a|b

Find a?

And also if x=2<<1 is given, then we can get x=4. But if 4=y<<1 is given Can we get y?

Answer 1

To begin with, these are just my observations and I have no sources to back them up. There are better ways, but the Wikipedia pages were really long and confusing so I hacked together this method.


Yes, you can, but you need more context (other equations to solve in reference to) and a lot more parsing. This is the method I came up with for doing this, but there are better ways to approach this problem. This was just conceptually easier for me.

Numbers

You can't just put an integer into an equation and have it work. Bitwise operators refer only refer to booleans, we just treat them as if they are meant for integers. In order to simplify an equation, we have to look at it as an array of booleans.

Taking for example an unsigned 8 bit integer:

a = 0b10111001

Now becomes:

a = {1, 0, 1, 1, 1, 0, 0, 1}

Parsing

Once you can get your equations to just booleans, then you can apply the actual bitwise operators to simple 1s and 0s. But you can take it one step further now, at this all bitwise equations can be written in terms of just AND, OR, and NOT. Addition, subtraction and multiplication can also be represented this way, but you need to manually write out the steps taken.

A ^ B = ~( ( A & B ) | ( (~A) & (~B) ) )

This includes bitshifts, but instead of expanding to other bitwise operators, they act as an assignment.

A = 0b10111001
B = 0b10100110
C = (A >> 2) ^ B

This then expands to 8 equations, one for each bit.

C[0] = A[2] ^ B[0]
C[1] = A[3] ^ B[1]
C[2] = A[4] ^ B[2]
C[3] = A[5] ^ B[3]
C[4] = A[6] ^ B[4]
C[5] = A[7] ^ B[5]
C[6] = 0 ^ B[6]
C[7] = 0 ^ B[7]

C[6] and C[7] can then be reduced to just B[6] and B[7] respectively.

Algebra

Now that you have an equation consisting of only AND, OR, and NOT, you can represent them using traditional algebra. In this step, they are no longer treated as bits, but instead as real numbers which just happen to be 0 or 1.

A | B => A + B - AB
A & B => AB
~A => 1 - A

Note that when plugging in 1 and 0, all of these remain true.

For this example, I will be using the Majority function as an example. It's job is to take in three bits and return 1 if there are more 1s than 0s.

It is defined as:

f(a, b, c) = ((a & b) | (a & c) | (b & c))

which becomes

f(a, b, c) = (ab + ac - (ab * ac)) + bc - (ab + ac - (ab * ac) * bc
f(a, b, c) = ab + ac + bc - a²bc - ab²c - abc² + a²b²c²

And now that you have this information, you can easily combine it with your other equations using standard algebra in order to get a solution. Any non 1 or 0 solution is extraneous.

Answer 2

A solution (if it exists) of such equation can be considered "unique" provided that you allow three states for each bit:

• bit is 0
• bit is 1
• does not matter X

E.g. 7 | 00001XXX(binary) = 15

Of course, such result cannot be converted to decimal.

For some operations it may be necessary to specify the bit width.