如何实现从逻辑移位算术右移? [英] How to implement arithmetic right shift from logical shift?

问题描述

我需要从逻辑移位，或xor和普通整数算术运算中实现32位算术右移.

I need to implement a 32-bit arithmetic right shift from logical shifts, and, or, xor and normal integer arithmetic operations.

我在某处阅读了以下内容:

I read somewhere the following is supposed to work:

(x>>N)|(((1<<N)-1)<<(32-N))

x是将要移位的整数，N是要移位的位数.

x is the integer that will be shifted and N is the amount of bits to shift.

这适用于负数(msb为1)，但不适用于正数(msb为0).

This works for negative (msb is 1) numbers but not for positive numbers (msb is 0).

有人知道有效的算法总是产生正确的结果吗?

Does anyone know an efficient algorithm that always produces the right result?

推荐答案

您可以使用此

(x >> N) | (-(x < 0) << (32 - N))

如果x为负数，则-(x < 0)返回-1，假设其补码为全1s . -1 << (32 - N)将产生一个值，在前N个位中全为1，在其余部分中全为0.如果x为非负数，则后半部分将始终为零，并且结果将与逻辑移位相同.或者，可以将其修改为

If x is negative then -(x < 0) returns -1, which have a bit pattern of all 1s, assuming 2's complement. -1 << (32 - N) will make a value which has all 1s in the top N bits and 0s in the remaining part. If x is non-negative then the latter part will always be zero, and the result will be the same as a logical shift. Alternatively it can be modified to

(x >> N) | ~(((x < 0) << (32 - N)) - 1)

请注意，它对于N <= 0或N> = 32无效(因为移动的距离超过了字体的宽度)调用UB )，因此您应在需要时专门处理这些情况

Note that it won't work for N <= 0 or N >= 32 (since shifting more than the width of type invokes UB) so you should treat those cases specifically if needed

如果不允许使用比较，则可以将x < 0更改为(unsigned)x >> 31并获得以下等效方法

If you're not allowed to use comparison then you can change x < 0 to (unsigned)x >> 31 and get the below equivalent ways

(x >> N) | (-((unsigned)x >> 31) << (32 - N))
(x >> N) | ((~0*(unsigned)x >> 31) << (32 - N))
(x >> N) | ~((((unsigned)x >> 31) << (32 - N)) - 1)

这篇关于如何实现从逻辑移位算术右移?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！