Bash 中的按位运算未按预期工作

Bash 中的按位运算未按预期工作

我遇到了一个奇怪的问题。为了演示,让我们取我机器上最大的无符号数(printf "%X \n" -1给我FFFFFFFFFFFFFFFF),并尝试移动一些位。首先,向左移动:

printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<4 ))
FFFFFFFFFFFFFFF0
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<8 ))
FFFFFFFFFFFFFF00
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<16 ))
FFFFFFFFFFFF0000

到目前为止,一切都很好。正如预期的那样。现在让我们尝试右移:

printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>4 ))
FFFFFFFFFFFFFFFF
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>8 ))
FFFFFFFFFFFFFFFF
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>16 ))
FFFFFFFFFFFFFFFF

等等,什么??为什么这不起作用?这是一个错误吗?


编辑:

我担心有人会建议与所提出的符号位有某种联系。但我们不是在谈论算术,因此符号的概念在这里没有地位。其他工具如*/用于算术。拥有一个可以操作位的工具的全部意义在于能够操作位——无论我稍后将如何选择显示这些位,无论是有符号的还是无符号的。正确的?喜欢:

printf "%u \n" -1
18446744073709551615

有人有什么想法吗?

编辑:

由于这里的答案直接讨论乘法或除法,让我尝试更清楚地解释我的担忧。乘法/除法和位移位是两个不同的东西,尽管我可以在长期程序员的头脑中看到它们之间的联系。做算术的时候,要有符号的概念;对于位移位你不需要。 Bash 为我们提供了两套截然不同的工具来处理这两种不同的事情。当我想要将一个数字乘以 2 时,我会伸手去拿这个*工具。事实上,Bash 在底层可以使用位移位进行算术,这一点已经超出了重点。

引用其中一个答案...

如果符号位没有被复制,结果将变成无符号数。例如,将 8 位值1111 0000向右移动一次将得到0111 1000

但变成1111 0000正是0111 1000我想要的。如果我想做除法,那么我会使用算术运算符。

无论如何,至少有某种方法可以明确指定移位时应该填充什么样的位?

答案1

两种不同的右移方式在共同使用中。

“逻辑右移”是在左边插入零位,因此右移一位的结果对应于无符号二进制数除以二。echo $(( 16 >> 1 ))给出8.

并且,“算术右移”在左侧插入了符号位的副本,因此右移一位的结果对应于除以二进制数除二。echo $(( 16 >> 1 ))给予8, 并echo $(( -16 >> 1 ))给予-8.除了在二进制补码上,它与实际除法的舍入不匹配:-15 >> 1给出-8;而-15 / 2给出-7.

如果符号位没有被复制,而是被清零,则结果将是正数。例如,将 8 位值1111 0000(0xf0, -16) 向右移动一次将得到0111 1000(0x78, +120)。


现在,使用其中哪一个是一个更棘手的问题。

实际上,许多实现都会对有符号数使用算术移位,而 shell 算术主要在有符号长整型上完成。

但这根本不能完全保证。 shell 算术的 POSIX 定义引用了大多数行为的 C 标准,例如,运算符表没有说明>>应该进行哪种类型的移位。 (看:Shell 命令语言,2.6.4 算术展开壳牌与公用事业公司,1.1.2 源自 ISO C 标准的概念:算术精度和运算

整数变量和常量,包括操作数和选项参数的值,[...]应实现为等同于 ISO C 标准有符号长数据类型 [...]

算术运算符和控制流关键字的实现应与引用的 ISO C 标准部分中的等效,[...]
<<,:>>第 6.5.7 节,按位移位运算符

cppreference.com 谈到 C 运算符

对于 negative a, 的值a >> b是实现定义的(在大多数实现中,这执行算术右移,因此结果保持负数)。

(这可能是一个世界的残余,其中并非所有东西都是二进制补码。对一个补码或符号量值向右移动将不同于对一个二进制补码数字向右移动。但结果是相同的:它是实现定义的。)

其他一些编程语言,像 JavaScript 一样,具有不同的算术右移>>和逻辑右移运算符>>>。但 C 没有,我尝试过的任何 shell 也没有。

另外,如果您进行偏移量大于字宽的移位,您也会看到奇怪的事情发生。在 x86 上,1 << 64只是1,因为处理器只查看移位值的最低 6 位,所以它与相同1 << 0。但是(1 << 32) << 320,结果在另一个处理器上可能会有所不同。


你说,

但符号的概念在这里没有立足之地。我的意思是,数字就是数字,无论稍后您选择将其显示为带符号还是不带符号,对吧?

对于补码机上的加法、减法和乘法的低位部分(例如 32x32 -> 32)也是如此。

但对于一般乘法或除法的高位部分来说,情况并非如此。 8 位值0xff可以表示无符号数 255 或有符号数 -1。例如,8x8 -> 16 乘法0xff * 0xff0x0001or 0xfe01,具体取决于它是有符号 (-1 * -1) 还是无符号 (255 * 255)。另外,例如0xff / 300x55,取决于它是否有符号(-1 / 3 == 0)或无符号(255 / 3 == 85)。

答案2

  • 逻辑右移用零填充,

    [01010110] >> 2 becomes [00010101]
    [11010110] >> 2 becomes [00110101]
    
  • 算术右移填充最高有效位,

    [01010110] >> 2 becomes [00010101]
    [11010110] >> 2 becomes [11110101]
    

您期望逻辑移位,但 Bash 执行算术移位。这确实与签名有关。

手动的

评估以固定宽度整数进行。运算符及其优先级、结合性和值与 C 语言中的相同。

整型常量遵循C语言定义,没有后缀或字符常量。以 0 开头的常量被解释为八进制数。前导“0x”或“0X”表示十六进制。

并引用自计算机系统,兰德尔·布莱恩特和大卫·奥哈拉伦:

C 标准没有精确定义应使用哪种类型的右移。对于无符号数据,右移必须符合逻辑。对于有符号数据(默认),可以使用算术或逻辑移位。 (...) 然而,在实践中,几乎所有编译器/机器组合都对有符号数据使用算术右移,并且许多程序员认为情况就是如此。

Stack Overflow 上也有人问过这个问题:C 中的移位运算符(<<、>>)是算术运算符还是逻辑运算符?

答案3

Bash 的行为与其他 shell 类似。尽管 shell 是一种相当高级的语言,但它提供有限大小的算术而不是普通的整数算术,这可以说是一个设计错误,但目前它不会改变。

数字就是数字,无论稍后您选择将其显示为有符号还是无符号,对吧?

是的,数字就是数字。但贝壳没有实际整数。他们只有机器整数,它们更加有限并且行为方式很奇怪。

乘法/除法和位移位是两个不同的东西,尽管我可以在长期程序员的头脑中看到它们之间的联系。做算术的时候,要有符号的概念;对于位移位你不需要。

事实上,它们是不同的,但又是相关的,而这正是你所误解的。位移位肯定有符号的概念!

机器整数可以用几种不同的方式解释:

  • 作为 N 个值位的数组。这就是记忆中的表示。
  • 作为位数组,第一个是符号位,另外 N-1 个是值位。符号位是 N 值位解释的最高有效位
  • 作为 0 到 2^N-1 之间的整数(“无符号整数”),其值由 N 个值位表示。
  • 为 -2^(N-1) 和 2^(N-1)-1 之间的整数(“有符号整数”),其值由 N-1 值位和符号位表示。如果符号位为 0,则该值由值位给出。如果符号位为 1,则该值为负数,理论上有多种方法可以根据值位计算该值,但实际上我不知道有任何平台运行 Unix shell 并执行除二进制补码。使用二进制补码表示时,符号位为 1 且值位代表的整数的值X是 - (2^(N-1) -X)。
  • 作为整数模 2^N(“整数模”)。该值为无符号值模 2^N。在二进制补码表示中,这也是模 2^N 的有符号值(这是二进制补码的主要优点)。

只要涉及的所有数字都在 0 到 2^N-1 之间,您可以选择任何解释,并且所有运算都会给出直观的结果。但是,如果操作数或结果超出此范围(负数或太大),则使用哪种解释很重要。

我将给出 N=4 (2^N = 16) 和二进制补码的示例,以保持示例的可读性。实际上,在现代版本的 bash 中,N=64。在古老版本的 bash 和其他 shell 中,N 在 32 位平台上可能是 32。

  • 数字解析以 2^N 为模进行。例如,当N=4时,319-13表示相同的数字,用位表示0011,而-313都用位表示1101
  • 八进制和十六进制打印将数字视为无符号整数。例如,具有位表示的数字1101以十六进制形式打印出来d:其第一位被解释为值位,而不是符号位。
  • 十进制打印将数字视为有符号整数。例如,具有位表示的数字1101以十六进制形式打印出来-3:其第一位被解释为符号位,而不是值位。
  • 加法、减法和乘法以 2^N 为模进行。这相当于对无符号整数或没有范围限制的有符号整数执行运算,然后在所需范围内取模 2^N 的余数。
  • 除法是对有符号整数执行的。与加法、减法和乘法不同,这种表示形式的选择很重要:使用无符号整数或数字模会给出不同的结果。 (有一个转折:(-2^(N-1) / -1) 是结果超出范围的唯一情况。据我所知,所有 shell 都给它值 -2^(N-1) ).)
  • 位运算对位表示进行操作。对于大多数操作,选择有符号或无符号表示并不重要:对所有位执行相同的操作。然而,对于轮班来说,它确实很重要,并且:
    • 左移将第一位视为值位。例如,位表示形式0111左移 1 的数字具有位表示形式1110。这使得左移k相当于乘以 2^k
    • 在我见过的所有 shell 中,右移将第一位视为符号位,该符号位将传播到值位上。例如,位表示形式1101右移 1 的数字具有位表示形式1110。这使得右移k相当于除以 2^k。这被称为算术移位, .
  • 比较适用于有符号整数。例如,用位表示的数字1111小于用位表示的数字0000,因为1111被认为是负数。

因此,回到 64 位示例,0xFFFFFFFFFFFFFFFF>>40xFFFFFFFFFFFFFFFF,因为>>将其左操作数解释为有符号位数组,并将设置的符号位传播到顶部打开的 4 个值位位置。操作与 完全相同-1 >> 4,因为-10xFFFFFFFFFFFFFFFF只是表示同一机器整数的不同方式。

答案4

看一看

由于第一个 1(左起)代表符号,因此只需将其复制即可。如果你试试:

printf "%X \n" $(( 0x7FFFFFFFFFFFFFFF>>4 ))

你可能会得到你所期望的。

相关内容