在C中实现逻辑右移

jpfvwuh4  于 9个月前  发布在  其他
关注(0)|答案(8)|浏览(70)

我正在用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,但我卡住了。

l7mqbcuq

l7mqbcuq1#

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

rslzwgfq2#

这就是你需要的:

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向右移动n bits。但是,如果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 << size1移动到最左边的位置:

  • *(1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

((0x1 << size) >> n) << 1将1复制到其n-1邻居:

  • *(11111000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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

  • (00000111 11111111 11111111)*

所以我们最终获得了一个掩码,从x >> n中提取真正需要内容:

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

&操作可以实现这一点。
这个函数的总成本是6操作。

ax6ht2ek

ax6ht2ek3#

只需将您的int存储在unsigned int中,并在其上执行>>
(The如果使用unsigned int,则不会扩展或保留符号)
http://en.wikipedia.org/wiki/Logical_shift

oug3syen

oug3syen4#

我认为问题出在你的“>>(n-1)”部分。如果n为0,则左部分将移位-1。我的解决方案是

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

mitkmikd5#

来源:php's implementation of logical right shifting

function logical_right_shift( i , shift ) {

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

    return i >> shift;
}

仅适用于32位平台。

mdfafbf1

mdfafbf16#

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作为最高有效位,而其他地方都是零,我们需要将0x1移位number of bits - 1。我提交我自己的答案,因为我对接受的答案的编辑被拒绝了。

ulmd4ohb

ulmd4ohb7#

和@伊格纳西奥的评论一样,我不知道你为什么要这样做(不像其他答案那样只转换为unsigned),但是(假设2的补码和二进制,并且有符号移位是算术的):

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

或:

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

xj3cbfub8#

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

仅适用于32位

相关问题