Maximum Xor Product

Reason bit by bit

In the common version, choose an n-bit value x to maximize (a xor x) * (b xor x). Bits above n are fixed. For a mutable bit where a and b agree, set the corresponding bit of x so both resulting numbers receive a one. Where they differ, exactly one result gets a one regardless of x; assign that one to the currently smaller partial result to keep the two factors balanced, processing from high bit to low bit.

Defend the greedy choice

A higher bit dominates every combination of lower bits, so decisions are made in descending order. When only one factor can receive the bit, balancing products is optimal for a fixed total. Build with a wide integer, then take the required modulus for the returned product; reducing intermediate comparison values modulo a number would destroy ordering. Complexity is O(n) time and O(1) extra space. Clarify bounds because language shifts and overflow behavior matter.