我一直在尝试为希尔伯特曲线图和逆图编写一个函数。幸运的是，上面有另一个 SE 帖子，接受的答案得到了高度评价，并且特色代码基于同行评审的学术期刊上的一篇论文。
不幸的是，我玩弄了上面的代码并查看了论文，但我不确定如何让它工作。似乎被破坏的是我的代码向后绘制了 2 位二维希尔伯特曲线的后半部分。如果你在最后一列画出二维坐标，你会向后看到曲线的后半部分（位置 8 及以上）。
我不认为我被允许发布原始 C 代码，但下面的 C++ 版本只是经过轻微编辑。我的代码中有一些不同的东西。
C 代码对类型不那么严格，所以我不得不使用
std::bitset除了@PaulChernoch在前面提到的 SE 帖子中提到的错误之外，下一个
for循环段错误也是如此。该论文奇怪地表示一维坐标。他们称其为数字的“转置”。我编写了一个从常规整数产生“转置”的函数。
这个算法的另一件事是：它不会产生单位间隔和单位超立方体之间的映射。相反，它扩展了问题并在间隔和具有单位间距的立方体之间映射。
NB: HTranspose is the representation of H they use in the paper
H, HTranspose, mappedCoordinates
------------------------------------
0: (00, 00), (0, 0)
1: (00, 01), (1, 0)
2: (01, 00), (1, 1)
3: (01, 01), (0, 1)
4: (00, 10), (0, 2)
5: (00, 11), (0, 3)
6: (01, 10), (1, 3)
7: (01, 11), (1, 2)
8: (10, 00), (3, 2)
9: (10, 01), (3, 3)
10: (11, 00), (2, 3)
11: (11, 01), (2, 2)
12: (10, 10), (2, 1)
13: (10, 11), (3, 1)
14: (11, 10), (3, 0)
15: (11, 11), (2, 0)
这是代码（在 C++ 中）。
#include <array>
#include <bitset>
#include <iostream>
#include <cmath>
namespace hilbert {
/// The Hilbert index is expressed as an array of transposed bits.
///
/// Example: 5 bits for each of n=3 coordinates.
/// 15-bit Hilbert integer = A B C D E F G H I J K L M N O is stored
/// as its Transpose ^
/// X[0] = A D G J M X[2]| 7
/// X[1] = B E H K N <-------> | /X[1]
/// X[2] = C F I L O axes |/
/// high low 0------> X[0]
template<size_t num_bits, size_t num_dims>
std::array<std::bitset<num_bits>,num_dims> TransposeToAxes(std::array<std::bitset<num_bits>,num_dims> X)
{
using coord_t = std::bitset<num_bits>;
using coords_t = std::array<coord_t, num_dims>;
coord_t N = 2 << (num_bits-1);
// Gray decode by H ^ (H/2)
coord_t t = X[num_dims-1] >> 1;
for(size_t i = num_dims-1; i > 0; i-- ) // https://stackoverflow.com/a/10384110
X[i] ^= X[i-1];
X[0] ^= t;
// Undo excess work
for( coord_t Q = 2; Q != N; Q <<= 1 ) {
coord_t P = Q.to_ulong() - 1;
for( size_t i = num_dims-1; i > 0 ; i-- ){ // did the same stackoverflow thing
if( (X[i] & Q).any() )
X[0] ^= P;
else{
t = (X[0]^X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
}
}
return X;
}
template<size_t num_bits, size_t num_dims>
std::array<std::bitset<num_bits>,num_dims> AxesToTranspose(std::array<std::bitset<num_bits>, num_dims> X)
{
using coord_t = std::bitset<num_bits>;
using coords_t = std::array<coord_t, num_dims>;
coord_t M = 1 << (num_bits-1);
// Inverse undo
for( coord_t Q = M; Q.to_ulong() > 1; Q >>= 1 ) {
coord_t P = Q.to_ulong() - 1;
for(size_t i = 0; i < num_bits; i++ ){
if( (X[i] & Q).any() )
X[0] ^= P;
else{
coord_t t = (X[0]^X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
}
} // exchange
// Gray encode
for( size_t i = 1; i < num_bits; i++ )
X[i] ^= X[i-1];
coord_t t = 0;
for( coord_t Q = M; Q.to_ulong() > 1; Q >>= 1 ){
if( (X[num_dims-1] & Q).any() )
t ^= Q.to_ulong()-1;
}
for( size_t i = 0; i < num_bits; i++ )
X[i] ^= t;
return X;
}
template<size_t num_bits, size_t num_dims>
std::array<std::bitset<num_bits>,num_dims> makeHTranspose(unsigned int H)
{
using coord_t = std::bitset<num_bits>;
using coords_t = std::array<coord_t, num_dims>;
using big_coord_t = std::bitset<num_bits*num_dims>;
big_coord_t Hb = H;
coords_t X;
for(size_t dim = 0; dim < num_dims; ++dim){
coord_t tmp;
unsigned c = num_dims - 1;
for(size_t rbit = dim; rbit < num_bits*num_dims; rbit += num_dims){
tmp[c] =Hb[num_bits*num_dims - 1 - rbit];
c--;
}
X[dim] = tmp;
}
return X;
}
} //namespace hilbert
int main()
{
constexpr unsigned nb = 2;
constexpr unsigned nd = 2;
using coord_t = std::bitset<nb>;
using coords_t = std::array<coord_t,nd>;
std::cout << "NB: HTranspose is the representation of H they use in the paper\n";
std::cout << "H, HTranspose, mappedCoordinates \n";
std::cout << "------------------------------------\n";
for(unsigned H = 0; H < pow(2,nb*nd); ++H){
// H with the representation they use in the paper
coords_t weirdH = hilbert::makeHTranspose<nb,nd>(H);
std::cout << H << ": ("
<< weirdH[0] << ", "
<< weirdH[1] << "), ("
<< hilbert::TransposeToAxes<nb,nd>(weirdH)[0].to_ulong() << ", "
<< hilbert::TransposeToAxes<nb,nd>(weirdH)[1].to_ulong() << ")\n";
}
}
关于另一篇文章，我注意到了一些奇怪的事情：
除了@PaulChernoch在上面提到的 SE 帖子中提到的错误之外，下一个
for循环段错误也是如此。没有人在谈论论文如何不提供单位间隔和单位立方体之间的映射，而是提供从整数到大立方体的映射，以及
我在这里没有看到任何关于论文用于无符号整数“转置”的奇怪表示。
如果你在最后一列画出二维坐标，你会向后看到曲线的后半部分（位置 8 及以上）。