使用位域或按位运算符在一个字节内移动一位
|
是否有一种优雅的方式在一个字节(或字/长)内移动一位。为简单起见,让我们使用一个简单的8位字节,而在该字节内仅移动一位。
给定一个位数,从0-7最小sig位到最大sig位(或者如果愿意,则为1-8位),我想从一个位置移到另一个位置:
7654 3210 <bit position
0101 1010 <some binary value
--x- --y- <move bit from x to y
0111 0100 <new value with x moved to y and intervening bits shifted left
因此,位位置5的x移至位位置1的y,位0,6,7保持不变。位2,3,4左移至\'make room \',位从5移至2。这仅是示例。
重要的是,钻头要移动,而不是与其目标互换。交换的比特示例很多,但这是微不足道的。
理想情况下,该解决方案将使用简单的位扭曲和按位运算符。假设语言不可知,简单的AND / OR / XOR,NOT,SHIFT左/右/ ROTATE或类似指令在任何组合中加上任何其他基本算术运算符(例如:mod,加法/减法等)都可以使用,甚至可以工作。代码就可以了。或者,位数组或位域类型的结构可能很简单。
除了实际的位移动之外,我还想找到一种方法:
向上或向下移动任何一点。
以任何方便的格式指定位数来源/目的地:例如:6> 2
表示向下移位,3> 7向上移位或起始位+/-偏移:6-4或3 + 4,或位加权:位6 = 64到位3 = 8。
可能从字节扩展到无符号的int,long等。
(理想情况下,可扩展
一次超过一个位,如果容易的话,可能是相邻位)
性能不是主要问题,但是优雅是足够快的。
我自己的细微方法是确定源和目标位的位置,决定是上移还是下移,进行移位复制,掩盖静态位并找到源位,合并静态和移位位,然后以某种方式设置/清除目标位。但是,尽管理论看起来不错,但优雅的实现超出了我的范围。
我意识到可以为一个字节建立一个预编译的查找表,但是如果要扩展为整数/长整数,这对我来说是不切实际的。
任何帮助表示赞赏。提前致谢。
没有找到相关结果
已邀请:
4 个回复
嘘伪
如果您认为此操作的更一般形式是使用三个参数“将剩余的位范围旋转一些”,则: 轮换中包含的最低有效位 轮换中要包含的最高有效位 旋转的位数 然后它将变成一个单一的基本原语,可以执行您想做的所有事情: 您显然可以移动任何位(选择适当的最低/最高有效位参数); 您可以向左或向右旋转,因为如果要旋转n位范围,则向右旋转k位与向左旋转n-k位是相同的; 它可以概括为任意位宽; 根据定义,我们可以一次旋转多于一个比特。 所以现在,所有需要的就是构造这个原始的... 首先,几乎可以肯定,我们关心的位需要一个位掩码。 我们可以通过将1向左移动n + 1位,然后减去1,来形成0至n位的掩码。 0-5位的掩码为(二进制):
...可以通过采用1:
...向左移动5 + 1 = 6位:
...再减去1可得出:
在C语言中,这将是
。但这至少对C而言是个微妙之处(当您将其标记为与语言无关时,我对此表示歉意,但这很重要,其他语言中也可能存在类似的问题):类型的宽度(或更多)会导致不确定的行为。因此,如果我们试图为8位类型的0-7位构造一个掩码,则计算将为
,这是未定义的。 (它可能在某些系统和某些编译器上有效,但不能移植。)在最终移入符号位的情况下,符号类型还存在未定义的行为问题。 幸运的是,在C语言中,我们可以通过使用
类型并将表达式写为
来避免这些问题。标准将无符号n位值的算术定义为以2n为模减少,并且所有单独的操作都定义明确,因此我们保证将获得正确的答案。 (题外话。) 好,现在我们有了一个掩码,用于位0-msb。我们想要为lsb-msb位做一个掩码,我们可以通过减去0-(lsb-1)位的掩码来完成,即mask10ѭ。例如
因此,掩码的最终表达式是:
可以通过掩码按位与选择要旋转的位:
...并且可以通过与AND一起使用反转掩码选择将保持不变的位:
旋转本身可以很容易地分为两个部分:首先,我们可以通过简单地向左旋转and15ѭ并丢弃掉掩码之外的任何位来获得旋转部分的最左边的位:
要获得最右边的位,请将(15ѭ向右旋转(n-shift)位,其中n是我们要旋转的位数(该n可计算为
):
可以通过组合
,
和ѭ22all中的所有位来获得最终结果:
您原来的示例将像这样工作(
为5,
为1,
为1):
这是另一个示例,输入值为16位,bit24ѭ= 15,
= 4,
= 4(这将旋转4位十六进制值的前3个十六进制数字):
土投
坛沤疲撑拆
那么您想要的号码是
。
唤副埂侧壬