Need help with a problem
51 minutes ago, Nineshadow said:That's what I was thinking as well, but then I realized it's not that simple.
Suppose you have
a=1011101
b=1101101
a<=b even if it has the 3rd bit (from the left) equal to 1, while b has it equal to 0. That's because the previous bit in a, which is more significant, is smaller than the previous bit in b.
So I thought about it this way:
Suppose I traverse the tree until I get to the most significant bit of b. I only go down the nodes which indicate a value of 0, since otherwise a would be bigger than b. Once I reach the most significant bit of b, I have two choices: If the bit in a is 0, then the rest of the binary representation of a could be whatever, because a<=b at that point. I can stop searching and add to the solutions. But if the bit in a is 1, then I must continue searching. So I search to the next most significant bit in b, going down only through the 0 nodes again, then do the same thing.
Maybe I described it incorrectly but the point is to traverse left to right (most to least significant), so my approach would stop at the second bit.
In terms of traversal, C++ code (havent tried to compile) would be (without the XOR):
void traverse( Node* node, std::uint32_t compValue, bool confirmedSmaller, std::vector<std::uint32_t>& results) { if (confirmedSmaller) { traverse(node->leftChild, 0, true, results); traverse(node->rightChild, 0, true, results); return; } std::uint32_t bit = compValue & (1 << 31); if ((bit >> 31) == node->value) { compValue <<= 1;// "Pop" the left most bit from the compare value traverse(node->leftChild, compValue, false, results); traverse(node->rightChild, compValue, false, results); } else if (bit > 0) { // Node contains 0, value to which we compare contains 1 // -> We're smaller than the value to which we compare traverse(node->leftChild, 0, true, results); traverse(node->rightChild, 0, true, results); }// else { // Node contains 1, value to which we compare contains 0 // -> We're larger than the value to which we compare //} }
EDIT:
With XOR I think traversal would be this:
void traverse( Node* node, std::uint32_t compValue, std::uint32_t mask, bool confirmedSmaller, std::vector<std::uint32_t>& results) { if (confirmedSmaller) { traverse(node->leftChild, 0, 0, true, results); traverse(node->rightChild, 0, 0, true, results); return; } std::uint32_t bit = (compValue & (1 << 31)) >> 31;// Get left most bit std::uint32_t maskBit = (mask & (1 << 31)) >> 31;// Get left most bit bit ^= maskBit;// Bitwise XOR if ((bit >> 31) == node->value) { compValue <<= 1;// "Pop" the left most bit from the compare value mask <<= 1;// Do the same for the mask traverse(node->leftChild, compValue, mask, false, results); traverse(node->rightChild, compValue, mask, false, results); } else if (bit > 0) { // Node contains 0, value to which we compare contains 1 // -> We're smaller than the value to which we compare traverse(node->leftChild, 0, 0, true, results); traverse(node->rightChild, 0, 0, true, results); }// else { // Node contains 1, value to which we compare contains 0 // -> We're larger than the value to which we compare //} }
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now