在C语言中实现逻辑右移

Question

我正在使用位运算符在C语言中实现逻辑右移函数，以下是我的代码：

int logical_right_shift(int x, int n)
{
    int size = sizeof(int); // size of int

    // arithmetic shifts to create logical shift, return 1 for true
    return (x >> n) & ~(((x >> (size << 3) - 1) << (size << 3) -1)) >> (n-1);
}

实际上，这适用于所有情况，除非n = 0。我一直在尝试找到一种方法来修复它，使其也适用于n = 0，但是我卡住了。

- Dan

---

你正在为有符号类型创建一个逻辑右移运算符？ - Ignacio Vazquez-Abrams

使用@Mark的建议，你可以将它改为以下内容（不能保证它能够正常工作）: return (n == 0 ? x : (x >> n) & ~(((x >> (size << 3) - 1) << (size << 3) -1)) >> (n-1)); - Mateen Ulhaq

@Dan：你想在答案中允许强制转换吗？ - Jeremiah Willcock

应该在没有强制转换或条件语句的情况下完成。 - Dan

这是应该作为家庭作业吗？ - Ignacio Vazquez-Abrams

Answer 1

int lsr(int x, int n)
{
  return (int)((unsigned int)x >> n);
}

- Ignacio Vazquez-Abrams

---

这是正确的答案（除了结果中不必要和丑陋的强制转换）。 对于负数的右移具有实现定义的行为（或者是实现定义的值？我忘记了），因此，任何使用有符号值上的 >> 运算符来实现您的 lsr 函数的实现都是不可移植的。 - R.. GitHub STOP HELPING ICE

这个解决方案存在一个问题：严格来说，在n==0的情况下，它具有实现定义的行为，因为如果原始值为负，则从int到unsigned的转换和再次转换会导致实现定义的行为。第一次转换必须在模UINT_MAX+1下进行，但是将其转换回有符号的int可能只是表示的重新解释，此时该值将被更改。 - R.. GitHub STOP HELPING ICE

@R.. 你好，能否给我一个例子或者一段代码片段，帮助我理解你的意思？谢谢。 - Jonguo

Answer 2

这就是你需要的:

int logical_right_shift(int x, int n)
{
    int size = sizeof(int) * 8; // usually sizeof(int) is 4 bytes (32 bits)
    return (x >> n) & ~(((0x1 << size) >> n) << 1);
}

解释

x >> n 表示将 x 向右移动 n 位。然而，如果 x 是负数，则符号位（最左边的位）将会被复制到右边，例如：

假设这里的每个 int 都是 32 位，让
x　　　　 =　-2147483648　(10000000 00000000 00000000 00000000)，则
x　>>　1　=　-1073741824　(11000000 00000000 00000000 00000000)
x　>>　2　=　-536870912　 (11100000 00000000 00000000 00000000)
依此类推。

因此，当 n 为负数时，我们需要消除那些多余的符号位。

这里假设 n = 5：

0x1 << size 将 1 移动到最左边的位置：

(10000000 00000000 00000000 00000000)

((0x1 << size) >> n) << 1 将 1 复制到其左侧 n-1 个邻居：

(11111000 00000000 00000000 00000000)

~((0x1 << size) >> n) << 1! 反转所有位：

(00000111 11111111 11111111 11111111)

因此，我们最终得到一个掩码以从 x >> n 中提取真正需要的内容：

(x >> n) & ~(((0x1 << size) >> n) << 1)

& 操作就能解决问题。

而这个函数的总成本是 6 次操作。

- mingyc

---

我认为这是正确的。但是你能左移32次吗？那将是一个未定义的移位？ - Timothy Leung

是的，如果 int 大小为 4 字节，那么这段代码会出错。他需要从 size 中减去 1，这样如果 int 是 4 字节，size 就是 31。 - modulitos

Answer 3

只需将您的int存储在unsigned int中，并对其执行>>操作。

（如果使用无符号整数，则不会扩展或保留符号）

http://en.wikipedia.org/wiki/Logical_shift

- Bernd Elkemann

Answer 4

我认为问题出在你的">> (n-1)"部分。如果n为0，则左侧部分将向左移动-1个位置。 所以，这是我的解决方案

int logical_right_shift(int x, int n)
{
  int mask = ~(-1 << n) << (32 - n);
  return  ~mask & ( (x >> n) | mask); 
}

- Levenson

---

这是一个优雅的解决方案，因为它不涉及任何条件语句，因此没有CPU分支。最终的 | mask 操作是不必要的，因为由那个OR操作设置为1的每个位都将被AND操作设置为0。掩码计算可以简化如下：int mask = int.MinValue >> (n - 1); 但是如果 n == 0，则我的简化会产生错误的结果，因此它取决于您的用例 - 这种简化不适用于库。 - radfast

Answer 5

源于php实现的逻辑右移

function logical_right_shift( i , shift ) {

    if( i & 2147483648 ) {
        return ( i >> shift ) ^ ( 2147483648 >> ( shift - 1 ) );
    }

    return i >> shift;
}

仅适用于32位平台。

- Ghulam Murtaza

Answer 6

Milnex的回答很好，解释得非常棒，但是实现不幸因为总大小的移位而失败了。这里是一个可行的版本：

int logicalShift(int x, int n) {
  int totalBitsMinusOne = (sizeof(int) * 8) - 1; // usually sizeof(int) is 4 bytes (32 bits)
  return (x >> n) & ~(((0x1 << totalBitsMinusOne) >> n) << 1);
}

要让二进制数的最高位为1，其余位都为0，我们需要将0x1左移位数-1位。我提交了自己的答案，因为我的修改被拒绝了。

- modulitos

Answer 7

与@Ignacio的评论一样，我不知道为什么你想这样做（除了像其他答案中那样进行无符号转换），但是如果假设是二进制补码和二进制位移，并且有符号位移是算术位移，那么怎么样：

(x >> n) + ((1 << (sizeof(int) * CHAR_BIT - n - 1)) << 1)

或者：

(x >> n) ^ ((INT_MIN >> n) << 1)

- Jeremiah Willcock

Answer 8

int logicalShift(int x, int n) {
  int mask = x>>31<<31>>(n)<<1;
  return mask^(x>>n);
}

仅适用于32位

- Toch

---

请添加更多信息以解释您的答案。这里不太接受仅有代码的答案。 - user6754053

@MarkYisri 这很讽刺，因为这个“线程”上得票最高的答案是仅有代码的，而且完美、清晰地回答了问题。 - MD XF

如果 x >> 31 的结果为非零值，则会导致未定义的行为。 - M.M