[geometry] Faster CellId::XY and CellId::FromXY.

2 files changed, 32 insertions, 0 deletions

diff --git a/base/base_tests/bits_test.cpp b/base/base_tests/bits_test.cpp
index 68e9d18048..4791164750 100644
--- a/base/base_tests/bits_test.cpp
+++ b/base/base_tests/bits_test.cpp
@@ -63,6 +63,32 @@ UNIT_TEST(PerfectShuffle)
   TEST_EQUAL(bits::PerfectUnshuffle(201547860), 557851022, ());
 }
 
+UNIT_TEST(BitwiseMerge)
+{
+  TEST_EQUAL(bits::BitwiseMerge(1, 1), 3, ());
+  TEST_EQUAL(bits::BitwiseMerge(3, 1), 7, ());
+  TEST_EQUAL(bits::BitwiseMerge(1, 3), 11, ());
+  TEST_EQUAL(bits::BitwiseMerge(uint32_t{1} << 31, uint32_t{1} << 31), uint64_t{3} << 62, ());
+
+  auto bitwiseMergeSlow = [](uint32_t x, uint32_t y) -> uint64_t {
+    uint64_t result = 0;
+    for (uint32_t i = 0; i < 32; ++i)
+    {
+      uint64_t const bitX = (static_cast<uint64_t>(x) >> i) & 1;
+      uint64_t const bitY = (static_cast<uint64_t>(y) >> i) & 1;
+      result |= bitX << (2 * i);
+      result |= bitY << (2 * i + 1);
+    }
+    return result;
+  };
+
+  for (uint32_t x = 0; x < 16; ++x)
+  {
+    for (uint32_t y = 0; y < 16; ++y)
+      TEST_EQUAL(bits::BitwiseMerge(x, y), bitwiseMergeSlow(x, y), (x, y));
+  }
+}
+
 UNIT_TEST(ZigZagEncode)
 {
   TEST_EQUAL(bits::ZigZagEncode(0),  0, ());
diff --git a/base/bits.hpp b/base/bits.hpp
index 26a742a794..42b0d5afb1 100644
--- a/base/bits.hpp
+++ b/base/bits.hpp
@@ -142,6 +142,12 @@ namespace bits
     return x;
   }
 
+  // Returns the integer that has the bits of |x| at even-numbered positions
+  // and the bits of |y| at odd-numbered positions without changing the
+  // relative order of bits coming from |x| and |y|.
+  // That is, if the bits of |x| are {x31, x30, ..., x0},
+  //         and the bits of |y| are {y31, y30, ..., y0},
+  // then the bits of the result are {y31, x31, y30, x30, ..., y0, x0}.
   inline uint64_t BitwiseMerge(uint32_t x, uint32_t y)
   {
     uint32_t const hi = PerfectShuffle((y & 0xFFFF0000) | (x >> 16));