Using Bit Packing for Fast Coordinate Lookup in C++

Checking whether a coordinate (x, y) exists is common in grid simulation problems.

Using normal pair storage:

set<pair<int, int>>

works, but lookup complexity becomes:

O(log n)

For large simulations, this can become slower.

Faster Approach

Instead of storing pairs directly, we can encode coordinates into a single 64-bit integer.

unordered_set<long long>

This gives average lookup complexity of:

O(1)

Encoding (x, y) into One Value

long long key =((long long)x <<32)|(unsigned int)y;

This stores:

• x in upper 32 bits
• y in lower 32 bits

Why This Works

A long long contains 64 bits.

We divide it into two halves:

|   x (32 bits)   |   y (32 bits)   |

Since both values occupy separate regions, the mapping becomes collision-free for 32-bit integers.

Why unsigned int is Important

Negative values use sign extension.

Without this:

(unsigned int)y

the lower bits may incorrectly affect upper bits after type promotion.

Correct version:

long long key =
    ((long long)x << 32) |
    (unsigned int)y;

This guarantees only lower 32 bits are used for y.

Storing keys

unordered_set<long long> mapi;
// here i will be like {x,y}
for (auto &i : arr) {
    long long temp=((long long)i[0]<<32)|(unsigned int)i[1] ; // (x+y)
        mapi.insert(temp) ; 
}

Checking Existence

long long key =
    ((long long)nx << 32) |
    (unsigned int)ny;
 
if (mapi.count(key)) {
    // key exists
}

Complexity Comparison

Why This method is powerful

This approach avoids:

• custom hash functions
• pair hashing overhead
• tree balancing overhead
• collision-prone manual encodings

Use case

https://leetcode.com/problems/walking-robot-simulation/description

Final Thoughts

At first glance this looks like a small optimization.

But in large simulations with frequent coordinate lookups, reducing:

O(log n) → O(1)

creates a noticeable performance improvement in time complexity.