7

我需要计算表示为char数组的位集之间的汉明距离。这是一项核心操作，因此必须尽可能快。我有这样的事情：

const int N = 32; // 32 always

// returns the number of bits that are ones in a char
int countOnes_uchar8(unsigned char v);

// pa and pb point to arrays of N items
int hamming(const unsigned char *pa, const unsigned char *pb)
{
  int ret = 0;
  for(int i = 0; i < N; ++i, ++pa, ++pb)
  {
    ret += countOnes_uchar8(*pa ^ *pb);
  }
  return ret;
}

profiling 之后，发现对ints 的操作比较快，所以写了：

const int N = 32; // 32 always

// returns the number of bits that are ones in a int of 32 bits
int countOnes_int32(unsigned int v);

// pa and pb point to arrays of N items
int hamming(const unsigned char *pa, const unsigned char *pb)
{
  const unsigned int *qa = reinterpret_cast<const unsigned int*>(pa);
  const unsigned int *qb = reinterpret_cast<const unsigned int*>(pb);

  int ret = 0;
  for(int i = 0; i < N / sizeof(unsigned int); ++i, ++qa, ++qb)
  {
    ret += countOnes_int32(*qa ^ *qb);
  }
  return ret;
}

问题

unsigned char *1）从投到unsigned int *安全吗？

2) 我在 32 位机器上工作，但我希望代码在 64 位机器上工作。sizeof(unsigned int)是在两台机器上返回 4，还是在 64 位机器上返回 8 ？

3) 如果sizeof(unsigned int)在 64 位机器中返回 4，我将如何在 64 位类型上操作long long？

4

2 回答 2

11

unsigned char *从投到unsigned int *安全吗？

形式上，它给出了未定义的行为。实际上，如果指针与unsigned int. 在某些平台上，如果对齐错误，它可能会失败或性能不佳。

sizeof(unsigned int)是在两台机器上返回 4，还是在 64 位机器上返回 8 ？

这取决于。有些平台有 64 位int，有些平台有 32 位。uint64_t无论平台如何使用都可能有意义；在 32 位平台上，您将有效地展开循环（每次迭代处理两个 32 位值），这可能会带来适度的改进。

我如何能够在 64 位类型上进行操作long long？

uint64_t，如果您有 C++11 或 C99 库。long long至少为 64 位，但在 2011 年之前的实现中可能不存在。

于 2013-09-06T13:18:20.563 回答
2

1）不，它不安全/不便携，它是未定义的行为。有些系统char大于一个字节，并且不能保证 char 指针正确对齐。

2）sizeof(int)理论上可能是64位机器上的任何东西。在实践中，它将是 4 或 8。

3)long long很可能是64 位，但也不能保证。如果您想要保证，请使用uint64_t. 但是，对于您的特定算法，我不明白为什么sizeof()数据块很重要。

考虑改用 stdint.h 中的类型，它们更适合可移植代码。代替 char、int 或 long long，使用uint_fast8_t. 这将使编译器以可移植的方式为您选择最快的整数。

作为旁注，您应该考虑将“countOnes”实现为查找表，在 4、8 或 32 位级别上工作，具体取决于最适合您的系统的内容。这将增加程序大小但减少执行时间。也许尝试实现某种形式的自适应查找表，它依赖于sizeof(uint_fast8_t).

于 2013-09-06T14:03:04.803 回答