我正在用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,但我卡住了。
8条答案
按热度按时间l7mqbcuq1#
rslzwgfq2#
这就是你需要的:
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 << size
将1
移动到最左边的位置:((0x1 << size) >> n) << 1
将1复制到其n-1
邻居:~((0x1 << size) >> n) << 1!
反转所有位:所以我们最终获得了一个掩码,从
x >> n
中提取真正需要内容:&
操作可以实现这一点。这个函数的总成本是
6
操作。ax6ht2ek3#
只需将您的
int
存储在unsigned int
中,并在其上执行>>
。(The如果使用unsigned int,则不会扩展或保留符号)
http://en.wikipedia.org/wiki/Logical_shift
oug3syen4#
我认为问题出在你的“>>(n-1)”部分。如果n为0,则左部分将移位-1。我的解决方案是
mitkmikd5#
来源:php's implementation of logical right shifting
仅适用于32位平台。
mdfafbf16#
Milnex的答案很棒,并且有一个很棒的解释,但不幸的是,由于总大小的变化,实现失败了。下面是一个工作版本:
为了让1作为最高有效位,而其他地方都是零,我们需要将
0x1
移位number of bits - 1
。我提交我自己的答案,因为我对接受的答案的编辑被拒绝了。ulmd4ohb7#
和@伊格纳西奥的评论一样,我不知道你为什么要这样做(不像其他答案那样只转换为
unsigned
),但是(假设2的补码和二进制,并且有符号移位是算术的):或:
xj3cbfub8#
仅适用于32位