C 旋转位域(需要解释)

Question

我想将一个字节向左旋转 1 位。我正在查看该网站的几个示例并发现了这段代码。虽然它有效，但我很感激任何一步一步了解它如何工作的信息。

unsigned int _rotl(const unsigned int value, int shift) 
{
    if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

首先，第一部分的作用是什么？对于最后一部分，不会移动那么多，您几乎会删除一些位吗？

例如:

说

value= 0x50    //01010000
shift = 4

我会有 对于

value << shift

01010000 << 4  =>   00000000

而对于 值 >> (sizeof(值)*8 - 移位)

01010000>> (4*8 - 4)   => 00000000

因此，对两者进行 OR 运算会给我 0。我的理解显然是错误的，但我很感激任何人为像我这样的初学者“简化”它。谢谢。

Answer 1

让我们一步一步来:

unsigned int _rotl(const unsigned int value, int shift) 
{
  if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?
    return value;
  return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

第一行:

if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?

该语句是一项优化和一项检查，合并为一行。如果满足两个条件之一，则返回 TRUE:

1. 移位为零(即不旋转任何位)
2. 由 shift 指定的旋转数不会有任何影响

否则该语句返回 FALSE，但也会计算实现所需结果所需的最小旋转次数，并将该值存储在 shift 中。 。换句话说，它计算shift = shift % size_of_integer_data_type .

例如，如果您有一个 32 位整数，则将其旋转 32 位不会产生任何作用。如果将其旋转 64、96 或 32 的任何其他倍数，也不会产生任何效果。如果我们的轮换没有任何效果，那么我们可以节省很多时间，然后尽早退出。

但是，我们也可能指定比必要的更多的工作。如果您有一个 32 位整数，则将其旋转一位与将其旋转 33 位、65 位或 97 位等具有相同的效果。此代码认识到这一事实，因此如果您将移位指定为 97 ，它重新分配 shift=1并删除无关的旋转。

声明sizeof(value)*8 - 1返回比 value 表示中的位数少 1 的值。例如，如果 sizeof(value)计算结果为 4(在具有 32 位整数的系统上)，然后 4*8 - 1 = 31 .

&=运算符是带有赋值的按位与。这意味着我们正在 shift 之间进行按位与运算。和sizeof(value)*8 - 1并将该结果分配给 shift 。与之前一样，该表达式的右侧等于 value 中的位数。减一。因此，这具有屏蔽 shift 的所有位的效果。大于 value 表示的大小，进而具有计算 shift = shift % size_of_integer_data_type 的效果。

具体来说，重新考虑 32 位情况。和以前一样，sizeof(value)*8-1计算结果为 31。按位计算，该值为 0000 0000 0000 0000 0000 0000 0001 1111 。该值与 shift 进行按位与运算。 shift 中的任何位的第 6 至 32 位设置为零，而第 1 至 5 位中的位保持不变。如果您指定 97 次旋转，结果将为 1 次。

  0000 0000 0000 0000 0000 0000 0110 0001 (97)
& 0000 0000 0000 0000 0000 0000 0001 1111 (31)
=========================================
  0000 0000 0000 0000 0000 0000 0000 0001 (1)

这里要做的最后一件事是回想一下，在 C 语言中，赋值语句的返回值就是被赋值的值。因此，如果 shift 的新值为零，则立即返回，否则继续。

第二行:

return (value << shift) | (value >> (sizeof(value)*8 - shift));

由于 C 没有旋转运算符(它只有左移和右移)，我们必须分别计算低位和高位，然后通过按位或将它们组合起来。这条线是单独计算每一边的简单问题。

声明value << shift计算高阶位。它将位模式向左移动 shift地方。另一个语句通过将位模式向右移动 size_of_integer_type - shift 来计算低位。位。这在示例中很容易看出。

假设value十进制值为 65535，shift值为 26。那么起始值为:

  0000 0000 0000 0000 1111 1111 1111 1111 (65535)

左移给我们:

  1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26)

右移给我们:

  0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6)

然后按位或组合这些结果:

  1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26)
| 0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6)
=========================================
  1111 1100 0000 0000 0000 0011 1111 1111 (65535 rot 26)

您可以重写此代码并获得相同的正确结果:

unsigned int _rotl(const unsigned int value, int shift)
{
    //Assume 8 bits in a byte
    unsigned bits_in_integer_type = sizeof(value)*8;
    shift = shift % bits_in_integer_type;

    if( shift == 0 ) return value; //rotation does nothing

    unsigned high_bits = value << shift;
    unsigned low_bits = value >> (bits_in_integer_type - shift);

    return high_bits | low_bits;
}