1

我正在寻找一种方法来反转字符数组中的字节。在将它们放置在正确的位置之前，我还需要反转正在交换的字节的各个位。例如，假设我有一个 char arr[1000]，其 arr[0] = 00100011 和 arr[999] = 11010110，我想交换 arr[0] 和 arr[999] 并反转每个位中的位。所以输出将是 arr[999]= 11000100（arr[0] 的反转位）和 arr[0] = 01101011（arr[999] 的反转位）。

我有一些代码可以在字节内进行位反转：

static  char reverseByte(char val)
{
    char result = 0;

    int counter = 8;
    while (counter-- < 0)
    {
        result <<= 1;
        result |= (char)(val & 1);
        val = (char)(val >> 1);
    }

    return result;
}

但这意味着运行一个外部循环来进行字节交换，然后为内部的每个字节运行上述小循环，即在上述情况下为 1000。这是正确的方法吗？有没有更好的方法来实现这一目标？任何帮助将不胜感激。

4

4 回答 4

1

这个怎么样？：

#include <stdio.h>
#include <limits.h>

#if CHAR_BIT != 8
#error char is expected to be 8 bits
#endif

unsigned char RevByte(unsigned char b)
{
  static const unsigned char t[16] =
  {
    0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
    0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
  };
  return t[b >> 4] | (t[b & 0xF] << 4);
}

void RevBytes(unsigned char* b, size_t c)
{
  size_t i;
  for (i = 0; i < c / 2; i++)
  {
    unsigned char t = b[i];
    b[i] = RevByte(b[c - 1 - i]);
    b[c - 1 - i] = RevByte(t);
  }
  if (c & 1)
    b[c / 2] = RevByte(b[c / 2]);
}

int main(void)
{
  int i;
  unsigned char buf[16] = 
  {
    0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
    0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
  };

  RevBytes(buf, 16);

  for (i = 0; i < 16; i++)
    printf("0x%02X ", buf[i]);
  puts("");

  return 0;
}

输出（ideone）：

0xF0 0xE0 0xD0 0xC0 0xB0 0xA0 0x90 0x80 0x70 0x60 0x50 0x40 0x30 0x20 0x10 0x00
于 2013-02-25T04:43:32.693 回答
0

反转集合的元素是一个古老的技巧 - 你交换 first 和 last，然后 first+1 和 last-1，然后......直到 first+i 等于或者比 last-j 更远。

所有你需要添加的是

-在交换它们之前翻转两个条目的位

- 如果中间还剩下一个元素，请当场翻转它的位

于 2013-02-25T04:32:59.657 回答
0

为此-假设您的位反转方法是正确的-如果您可以节省额外char的存储空间，则可以简单地遍历字节。考虑以下方法：

static void swapReverseBytes(char* arr, size_t len)
{
  int i = 0;
  char tmp = 0;
  if(arr == NULL || len < 1)
    return;
  if(len == 1) {
    arr[0] = reverseByte(arr[0]);
    return;
  }
  for(i = 0 ; i < (len / 2) ; ++i) {
    tmp = arr[len - i - 1];
    arr[len - i - 1] = reverseByte(arr[i]);
    arr[i] = reverseByte(tmp);
  }
}

这是一个粗略的草图（我认为应该编译），假设我没有错误，这应该可以工作。如前所述，使用 a 反转位可能是最快的LUT，但字节交换方法将相对相似，因为您需要实际移动每个字节，除非您保留有关数组遍历顺序的某些状态。如果是这种情况，很可能简单地使用某种状态（即标志）来确定是应该正常遍历数组（1...n）还是以相反的顺序（n...1）遍历数组。无论如何，交换在 Big-O 中是“免费的”，但实际上可能（不一定）显示出性能影响。所以如果你的优化真的是速度和额外的int在太空中并不算多，这种状态对你来说可能是值得的。请注意，此技巧仅在这是内部的情况下才有效。如果这个方法对用户是公开的并且他或她不知道这个标志，那么这实际上不会翻转任何东西。使用它的另一个选项是，如果您可以使用C++，您可以创建一个为用户封装此功能的类。

于 2013-02-25T04:44:17.820 回答
0

为此-假设您的位反转方法是正确的-如果您可以节省额外char的存储空间，则可以简单地遍历字节。考虑以下方法：

static void swapReverseBytes(char* arr, size_t len)
{
  int i = 0;
  char tmp = 0;
  if(arr == NULL || len < 1)
    return;
  if(len == 1) {
    arr[0] = reverseByte(arr[0]);
    return;
  }
  for(i = 0 ; i < (len / 2) ; ++i) {
    tmp = arr[len - i - 1];
    arr[len - i - 1] = reverseByte(arr[i]);
    arr[i] = reverseByte(tmp);
  }
}

这是一个粗略的草图（我认为应该编译），假设我没有错误，这应该可以工作。如前所述，使用 a 反转位可能是最快的LUT，但字节交换将相对相似，因为您需要实际移动每个字节，除非您保留有关数组遍历顺序的某些状态。如果是这种情况，很可能简单地使用某种状态（即标志）来确定是应该正常遍历数组（1...n）还是以相反的顺序（n...1）遍历数组。无论如何，交换在 Big-O 中是“免费的”，但实际上可能（不一定）显示性能影响（因为不会有“实际的”字节顺序交换）。请注意，如果用户期望一个已排序的数组，这将不起作用 - 此技巧仅在这是内部的情况下有效（或者您有某种封装，例如在C++类中）。

于 2013-02-25T04:47:41.123 回答