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.

Answer 3

you can find an a that solves the equation, but it will not be unique. assume b=c=1 then a=0 and a=1 are solutions. for c=1, b=0 there will be no solution. this is valid for all the bits in the numbers you consider. if the equation is solvable a=c will be (one of the) solution(s).

and left-shifting an integer will always result in an even integer (the least-significant bit is zero). so this only works for even itegers. in that case you can invert the operation by applying a right-shift (>>).

Answer 4

For your particular cases, the answer is no, you cannot solve or 'undo' the OR-operation (|) and shifting left or right (<<, >>) since in both cases information is lost by applying the operation. For example, 8|7=15 and 12|7=15, thus given the 7 and 15 it is not possible to obtain a unique solution.

An exception is the XOR operation, for which does hold that when a^b=c, then b^c=a and a^c=b.