6

我偶然发现了一个问题，询问您是否曾经在实际项目中使用过位移。我在许多项目中都广泛使用了位移，但是，我从来不必使用算术位移，即左操作数可能为负并且符号位应该移入而不是零的位移。例如，在 Java 中，您将使用运算符进行算术位移>>（而>>>将执行逻辑移位）。经过深思熟虑，我得出的结论是，我从未使用>>过可能为负的左操作数。

正如这个答案中所述，算术移位甚至是在 C++ 中定义的实现，因此 - 与 Java 相比 - C++ 中甚至没有用于执行算术移位的标准化运算符。答案还说明了一个有趣的问题，即我什至不知道的负数移位问题：

+63 >> 1 = +31 (integral part of quotient E1/2E2)
00111111 >> 1 = 00011111
-63 >> 1 = -32 
11000001 >> 1 = 11100000

所以-63>>1产量-32在查看位时是显而易见的，但可能不是大多数程序员一见钟情。更令人惊讶（但在查看这些位时再次明显）是-1>>1，-1不是0。

那么，可能负值的算术右移的具体用例是什么？

4

6 回答 6

7

也许最著名的是无分支绝对值：

int m = x >> 31;
int abs = x + m ^ m;

它使用算术移位将符号位复制到所有位。我遇到的大多数算术移位都是这种形式。当然，这不需要算术移位，您可以将所有出现的x >> 31(where xis an int)替换为-(x >>> 31).

值 31 来自intin bits 的大小，在 Java 中定义为 32。因此，右移 31 会移出除符号位之外的所有位，符号位（因为它是算术移位）被复制到这 31 位，在每个位置留下符号位的副本。

于 2014-07-31T11:47:56.263 回答
1

这是一个函数示例，它将找到大于或等于输入的 2 的最小幂。这个问题还有其他可能更快的解决方案，即任何面向硬件的解决方案或只是一系列右移和 OR。此解决方案使用算术移位来执行二进制搜索。

unsigned ClosestPowerOfTwo(unsigned num) {
  int mask = 0xFFFF0000;
  mask = (num & mask) ? (mask << 8) :  (mask >> 8);
  mask = (num & mask) ? (mask << 4) :  (mask >> 4);
  mask = (num & mask) ? (mask << 2) :  (mask >> 2);
  mask = (num & mask) ? (mask << 1) :  (mask >> 1);
  mask = (num & mask) ?  mask       :  (mask >> 1);
  return (num & mask) ? -mask       : -(mask << 1);
}
于 2014-08-03T23:46:39.790 回答
1

它以前对我有用，用于创建蒙版，然后在“&”或“|”中使用 操作位域时的运算符，用于按位数据打包或按位图形。

我没有方便的代码示例，但我确实记得很多年前在黑白图形中使用该技术进行放大（通过扩展一点，1 或 0）。对于 3 倍变焦，“0”将变为“000”，“1”将变为“111”，而无需知道该位的初始值。要扩展的位将放置在高位位置，然后算术右移将扩展它，无论它是 0 还是 1。逻辑移位，无论是左移还是右移，总是带入零来填充空出的位位置. 在这种情况下，符号位是解决方案的关键。

于 2014-07-31T10:49:05.703 回答
0

Indeed logical right shift is much more commonly used. However there are many operations that require an arithmetic shift (or are solved much more elegantly with an arithmetic shift)

  • Sign extension:

    • Most of the time you only deal with the available types in C and the compiler will automatically sign extend when casting/promoting a narrower type to a wider one (like short to int) so you may not notice it, but under the hood a left-then-right shift is used if the architecture doesn't have an instruction for sign extension. For "odd" number of bits you'll have to do the sign extension manually so this would be much more common. For example if a 10-bit pixel or ADC value is read into the top bits of a 16-bit register: value >> 6 will move the bits to the lower 10 bit positions and sign extend to preserve the value. If they're read into the low 10 bits with the top 6 bits being zero you'll use value << 6 >> 6 to sign extend the value to work with it
    • You also need signed extension when working with signed bit fields 
      struct bitfield {
    int x: 15;
    int y: 12;
    int z: 5;
};

int f(bitfield b) {
    return (b.x/8 + b.y/5) * b.z;
}
      Demo on Godbolt. The shifts are generated by the compiler but usually you don't use bitfields (as they're not portable) and operate on raw integer values instead so you'll need to do arithmetic shifts yourself to extract the fields
    • Another example: sign-extend a pointer to make a canonical address in x86-64. This is used to store additional data in the pointer: char* pointer = (char*)((intptr_t)address << 16 >> 16). You can think of this as a 48-bit bitfield at the bottom
    • V8 engine's SMI optimization stores the value in the top 31 bits so it needs a right shift to restore the signed integer

  • Round signed division properly when converting to a multiplication, for example x/12 will be optimized to x*43691 >> 19 with some additional rounding. Of course you'll never do this in normal scalar code because the compiler already does this for you but sometimes you may need to vectorize the code or make some related libraries then you'll need to calculate the rounding yourself with arithmetic shift. You can see how compilers round the division results in the output assembly for bitfield above

  • Saturated shift or shifts larger than bit width, i.e. the value becomes zero when the shift count >= bit width

    uint32_t lsh_saturated(uint32_t x, int32_t n) // returns 0 if n == 32
{
    return (x << (n & 0x1F)) & ((n-32) >> 5);
}

uint32_t lsh(uint32_t x, int32_t n) // returns 0 if n >= 32
{
    return (x << (n & 0x1F)) & ((n-32) >> 31);
}

  • Bit mask, useful in various cases like branchless selection (i.e. muxer). You can see lots of ways to conditionally do something on the famous bithacks page. Most of them are done by generating a mask of all ones or all zeros. The mask is usually calculated by propagating the sign bit of a subtraction like this (x - y) >> 31 (for 32-bit ints). Of course it can be changed to -(unsigned(x - y) >> 31) but that requires 2's complement and needs more operations. Here's the way to get the min and max of two integers without branching:

    min = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
max = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));

    Another example is m = m & -((signed)(m - d) >> s); in Compute modulus division by (1 << s) - 1 in parallel without a division operator

于 2020-11-07T06:08:44.833 回答
-1

我不太清楚你的意思。但是，我将推测您想将位移位用作算术函数。我看到的一件有趣的事情是二进制数的这个属性。

int n = 4;
int k = 1;

n = n << k; // is the same as n = n * 2^k
//now n = (4 * 2) i.e. 8
n = n >> k; // is the same as n = n / 2^k
//now n = (8 / 2) i.e. 4

希望有帮助。

但是是的，你要小心我会掩盖的负数，然后相应地把它转回来

于 2014-07-31T11:05:45.643 回答
-1

在 C 语言中，当编写设备驱动程序时，移位运算符被广泛使用，因为位被用作需要打开和关闭的开关。位移允许人们轻松正确地瞄准正确的开关。

许多散列和加密函数都使用位移位。看看Mercenne Twister。

最后，有时使用位域来包含状态信息很有用。包括位移在内的位操作功能对这些事情很有用。

于 2014-07-31T11:16:43.213 回答