Bit Manipulation - Maximum XOR of Two Numbers
Given the final maximum XOR value is 15 for an input array of 4-bit numbers, and the prefix set at bit 3 iteration is {0, 8, 7, 15}, which pair of numbers could have produced this maximum XOR?
Given the final maximum XOR value is 15 for an input array of 4-bit numbers, and the prefix set at bit 3 iteration is {0, 8, 7, 15}, which pair of numbers could have produced this maximum XOR?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Maximum XOR is 15 (binary 1111), so pair differs in all 4 bits.
0 (0000) XOR 15 (1111) = 15.Step 2: Check pairs: 8 (1000) XOR 7 (0111) = 15, 0 XOR 15 = 15, 7 XOR 15 = 8, 8 XOR 15 = 7.
Only 0 and 15 or 8 and 7 produce 15.Step 3: Given prefix set includes 8 and 7, the pair 8 and 7 is valid and matches prefix set.
8 and 7 is correct.Final Answer:
Option B -> Option BQuick Check:
8 ^ 7 = 15 matches max XOR [OK]
Quick Trick: Max XOR 15 means pair differs in all bits [OK]
Common Mistakes:
MISTAKES- Picking pairs that don't XOR to max value
Trap Explanation:
PITFALL- Candidates confuse which pairs produce max XOR from prefix sets.
Interviewer Note:
CONTEXT- Tests reverse reasoning from output to input pairs.
Master "Maximum XOR of Two Numbers" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes