2

不久前我做了一个关于四叉树寻路的项目，我想提高它的性能。似乎使用 tesseral 算术来确定节点邻接（根据此页面，由不列颠哥伦比亚大学地理系提供）将比我目前使用的蛮力方法快得多（我正在检查共享边，这对于静态四叉树效果很好，但如果地图发生变化，开销会太大）。

我或多或少理解邻接算法部分所说的内容，但我不确定如何开始。我主要对 C# 感兴趣，但如果已经有一些源代码可以处理我可以查看的 tesseral 算术，那将是非常棒的，无论语言如何。否则，谁能给我一些关于处理加/减进位的指示？

4

2 回答 2

4

好吧，我不知道有什么方法可以有效地做到这一点，但通常的“按位运算相加”算法建议使用以下算法（未经测试）：

static int tesseral_add(int x, int y)
{
    int a, b;
    do
    {
        a = x & y;
        b = x ^ y;
        x = a << 2; // move carry up 2 places instead of the usual 1
        y = b;
    } while (b != 0);
    return b;
}

如果有进位链，它可能会循环很多。

实际上，有一个更好的方法可以做到这一点。

观察 for z = interleave(a, -1); w = interleave(b, 0);，添加z和w直接给出部分正确的结果，因为任何进位都会重新进位（所有“中间”位都是 1）。唯一的“问题”是它破坏了 y 坐标。

因此，要添加两个 tesseral numbers z = interleave(a, b); w = interleave(c, d);，有一个很好的简短方法：

int xsum = (z | 0xAAAAAAAA) + (w & 0x55555555);
int ysum = (z | 0x55555555) + (w & 0xAAAAAAAA);
int result = (xsum & 0x55555555) | (ysum & 0xAAAAAAAA);
于 2012-02-21T11:56:15.197 回答
2

我认为，处理镶嵌算术的最简单方法是“位解压缩”数字，正常执行任意数量的算术运算，并在需要镶嵌形式时将它们“位压缩”回来：

z = bit_zip(bit_unzip(x) + bit_unzip(y));

（此示例unsigned仅适用于。对于有符号整数，将每个数字解压缩为两个变量并分别对两个部分进行正常算术）。

您可以在“计算事项 ”第 1.15 章“按位压缩”中找到“位解压缩”和“位压缩”的快速实现。

于 2012-02-21T17:09:35.423 回答