Bit Manipulation - Maximum XOR of Two Numbers
Suppose the input array can contain negative integers as well as positive integers. Which modification to the trie-based maximum XOR algorithm is necessary to correctly handle negative numbers?
Suppose the input array can contain negative integers as well as positive integers. Which modification to the trie-based maximum XOR algorithm is necessary to correctly handle negative numbers?
hard🎤 Interviewer Follow-up Q15 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand negative number representation
Negative numbers use two's complement, so their bit patterns differ from unsigned integers.Step 2: Convert to unsigned 32-bit representation
By masking with 0xFFFFFFFF, negative numbers become unsigned 32-bit integers, allowing consistent trie insertion and XOR calculation.Step 3: Avoid using absolute values or larger bit widths
Absolute values lose sign info; larger bit widths are unnecessary and inefficient.Final Answer:
Option B -> Option BQuick Check:
Unsigned 32-bit masking ensures correct bitwise trie operations [OK]
Quick Trick: Mask negatives to unsigned 32-bit for trie [OK]
Common Mistakes:
MISTAKES- Ignoring sign bits
- Using absolute values
- Assuming 64-bit needed
Trap Explanation:
PITFALL- Option A looks plausible but negative bits differ; option C correctly normalizes bits.
Interviewer Note:
CONTEXT- Tests candidate's understanding of bitwise representation and edge cases.
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