Whats the reverse function of x XOR (x/2)?

Question

Whats the reverse function of x XOR (x/2)?

Is there a system of rules for equation solving, similar to algebra, but with logic operators?

Answer 1

Suppose we have a number x of N bits. You could write this as:

b(N-1) b(N-2) b(N-3) ... b(0)

where b(i) is bit number i in the number (where 0 is the least significant bit).

x / 2 is the same as x shifted left 1 bit. Let's assume unsigned numbers. So:

x / 2 = 0 b(N-1) b(N-2) ... b(1)

Now we XOR x with x / 2:

x ^ (x / 2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1)

Note that the rightmost bit (the most significant bit) of this is b(N-1)^0 which is b(N-1). In other words, you can get bit b(N-1) from the result immediately. When you have this bit, you can calculate b(N-2) because the second bit of the result is b(N-2)^b(N-1) and you already know b(N-1). And so on, you can compute all bits b(N-1) to b(0) of the original number x.

Answer 2

I can give you an algorithm in bits:

Assuming you have an array of n bits:

b = [b1 .. bn] // b1-bn are 0 or 1

The original array is:

x0 = b0
x1 = b1 ^ x0
x2 = b2 ^ x1

or in general

x[i] = b[i] ^ x[i-1]

Answer 3

Assume Y = X ^ (X / 2)

If you want to find X, do this

X = 0

do

  X ^= Y
  Y /= 2

while Y != 0

I hope it helps!