What is the inverse function x XOR (x / 2)?

Question

What is the inverse function x XOR (x/2) ?

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

Answer 1

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

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

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

x / 2 matches x left-shifted 1 bit. Let them accept unsigned numbers. So:

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

Now we are 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 (most significant bit) of this b(N-1)^0 , which is equal to b(N-1) . In other words, you can immediately get bit b(N-1) from the result. 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) 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 

Source array:

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

or even

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

Answer 3

Suppose Y = X ^ (X / 2)

If you want to find X do it

 X = 0 do X ^= Y Y /= 2 while Y != 0 

Hope this helps!

Answer 4

I know this is an old topic, but I came across the same question and I found a little trick. If you have bit n , instead of having to perform n bits operations (for example, Jesper's answer), you can do this with log2 (n) number :

Assuming y is equal to x XOR (x / 2) at the beginning of the program, you can execute the following C program:

 INPUT : y int i, x; x = y; for (i = 1; i < n; i <<= 1) x ^= x >> i; OUTPUT : x 

and here you have a solution.

• "→" - operation of the right shift of bits. For example, the number 13, 1101 in binary, if it is shifted by 1 on the right, will become 110 in binary, so 13 → 1 = 6. x → i is equivalent to x / 2 ^ i (division by integers, of course)
• "<<" - operation to shift the left bit (i <= 1 is equivalent to i * = 2)

Why does this work? Take n = 5 bits as an example and start with y = b4 b3 b2 b1 b0 (in binary format: in the next x is also written in binary, but I am written in decimal)

• Initialization:

x = b4 b3 b2 b1 b0

• First step: i = 1

x → 1 = b4 b3 b2 b1, so we have (b2 ^ b3) (b1 ^ b2) (b0 ^ b1)

• Second step: i = 2

x → 2 = b4 (b3 ^ b4) (b2 ^ b3), so we have x = b4 (b3 ^ b4) (b2 ^ b3) (b1 ^ b2) (b0 ^ b1) XOR b4 (b3 ^ b4) (b2 ^ b3) = b4 (b3 ^ b4) (b2 ^ b3 ^ b4) (b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3)

• Third step: i = 4

x → 4 = b4, so we have x = b4 (b3 ^ b4) (b2 ^ b3 ^ b4) (b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3) XOR b4 = b4 (b3 ^ b4 ) (b2 ^ b3 ^ b4) (b1 ^ b2 ^ b3 ^ b4) (b0 ^ b1 ^ b2 ^ b3 ^ b4)

• Then I = 8, which is more than 5, we exit the cycle.

And we have the desired result.

There are log2 (n) iterations in the loop, because I start with 1 and multiply by 2 at each step, so in order for me to reach n, we have to do it log2 (n) times.