Introduction

In programming notation, ^ almost always means bitwise XOR, not exponentiation. That changes this problem completely. For z = x ^ (x << y), the inverse is not something you derive with logarithms. You recover it by reconstructing the bits of x in the right order.

Understand the Bit Dependency

Assume y is fixed and you are working with a fixed-width unsigned integer. The expression says that each bit of z is the XOR of:

• the corresponding bit of x
• the bit of x that is y positions lower, shifted into place

If bit positions are zero-based, then:

• when i < y, the shifted term contributes zero, so z_i = x_i
• when i >= y, z_i = x_i xor x_(i-y)

That recurrence is the whole inverse. The low y bits come straight from z, and every later bit can be solved once the earlier bits are known.

Recover x from Low Bits to High Bits

Because a left shift depends on lower-order bits, inversion proceeds from least significant bit upward. That is why this transform shows up in XOR-shift style algorithms: it is simple to apply and still reversible when the width is known.

1def forward(x: int, shift: int, width: int) -> int:
2    mask = (1 << width) - 1
3    return (x ^ ((x << shift) & mask)) & mask
4
5
6def invert_left_xor(z: int, shift: int, width: int) -> int:
7    result = 0
8
9    for bit_index in range(width):
10        z_bit = (z >> bit_index) & 1
11
12        if bit_index < shift:
13            x_bit = z_bit
14        else:
15            prior_bit = (result >> (bit_index - shift)) & 1
16            x_bit = z_bit ^ prior_bit
17
18        result |= x_bit << bit_index
19
20    return result
21
22
23original = 0b10110110
24encoded = forward(original, shift=3, width=8)
25decoded = invert_left_xor(encoded, shift=3, width=8)
26
27print(bin(encoded))
28print(bin(decoded))
29print(decoded == original)

The critical line is x_bit = z_bit ^ prior_bit. Once you have already reconstructed the earlier bit at i - shift, the current bit follows immediately.

Walk Through a Small Example

Take x = 0b10110110 with y = 3. The first three bits of z match the first three bits of x because there is no shifted contribution yet. Starting at bit index 3, each new bit of z mixes the current bit of x with a previously seen bit of x.

That means inversion is deterministic:

1. copy the first y bits directly
2. solve each later bit with XOR against the already recovered bit y positions earlier

This is much simpler than brute force, and it scales linearly with the word size.

Fixed Width Is Part of the Problem

Python integers are unbounded, but machine-level bit tricks usually assume a fixed width such as 8, 16, 32, or 64 bits. That is why the masking step matters.

1value = 0b1111000011110000
2width = 16
3mask = (1 << width) - 1
4
5encoded = (value ^ (value << 5)) & mask
6decoded = invert_left_xor(encoded, shift=5, width=16)
7
8print(decoded == value)

If you forget the mask in a fixed-width setting, high bits that should have been discarded can leak into the result and make the inverse look wrong.

Right-Shift Versions Reverse in the Other Direction

The idea changes slightly for z = x ^ (x >> y). In that case, higher bits influence lower bits, so reconstruction goes from the most significant side down to the least significant side.

That gives a useful mental rule:

• invert x ^ (x << y) from low bits to high bits
• invert x ^ (x >> y) from high bits to low bits

Once you think in terms of bit dependencies rather than algebra, the inverse becomes straightforward.

Common Pitfalls

• Reading ^ as exponentiation instead of bitwise XOR.
• Forgetting that the inverse assumes a fixed shift amount.
• Ignoring the word width and skipping masking in fixed-width code.
• Recovering bits in the wrong direction for the type of shift used.
• Trying brute force when the bit recurrence gives a direct inverse.

Summary

• 'z = x ^ (x << y) is a reversible XOR-shift transform, not an exponential function.'
• The first y bits of z are copied directly from x.
• Each later bit can be recovered with x_i = z_i xor x_(i-y).
• Inversion proceeds from low bits to high bits for left shifts.
• Fixed-width masking is essential when the original operation assumes machine-size integers.