需要帮助来理解此代码以找到给定数字中1的位置

Question

以下代码帮助我们找到给定数字中一位的位置:

    int n = in.nextInt();
    for (int d = 30; d >= 0; d--){
        if (n << ~d < 0){
            System.out.print(d + " ");
        }
    }

例如:如果n = 5,则其二进制表示为101,并且1s位于第0和第2位置,因此输出将为2 0.

更多例子:

n        Output
8        3
149      7 4 2 0

我无法理解此代码的含义:

n << ~d < 0.

我知道右移和恭维的概念,但想知道当n位置设置有位时,这个特定表达式如何评估为负数d.

Answer 1

这段代码看起来比它看起来更棘手,看起来它被设计成在更简单的算术运算可能更清晰的地方使用按位运算.

因为Java中的整数用带符号的二进制补码表示来表示,所以取一个数字的按位补码相当于否定它并添加一个.以数学方式重述:

~x = -x + 1

这意味着代码

n << ~d

相当于

n << (-d + 1).

现在这很奇怪,因为这意味着你左移了一个负数......这没有多大意义.这是我们需要转到关于这个主题的Java语言规范的地方,其中说明左移:

如果左侧操作数的提升类型是int,则只使用右侧操作数的五个最低位作为移位距离.就好像右手操作数受到按位逻辑AND运算符&(§15.22.1)和掩码值0x1f(0b11111)的影响.因此,实际使用的移位距离始终在0到31的范围内,包括0和31.

换句话说,移位操作完全忽略除数字值的底部五位之外的所有内容.这意味着我们实际上并没有转移负数 - 我们正在转移正数,具体数量取决于数量的最低5位~d.(我正在转回使用补语而不是负值,因为在这一点上,似乎算术解释~d可能并不那么有用.)

如果我们取数字d,翻转所有位,然后只关注最低的五位,它最终相当于评估31-d.为了看到这一点,请注意31具有二进制表示11111,因此如果我们从11111开始并减去数字d,则每1位被翻转为0(1 - 1 = 0)并且每个零位被翻转为1 (1 - 0 = 1).换句话说,表达

n << ~d

在这种情况下,完全等同于

n << (31 - d)

因为d总是在0到31之间.

这现在让我们更多地了解这里发生了什么.请记住,在一个带符号的32位整数表示中,整数的第一位是符号位.如果为1,则该值为负,如果为0,则该值为非负.因此,如果我们采用n并将其向前移动31-d位置,那么我们将数字的第d位推入第一位位置(如果不清楚为什么,请稍微调整一下).如果第d位为1,则设置符号位并使数字为负,如果第d位为0,则将符号位设置为零并使该数字为非负数.这就是为什么

(n << ~d) < 0

测试该位是否设置 - 它检查原始位置的1位是否触发结果数中的符号位.

说完这一切之后,我觉得这比现在要复杂得多.通过屏蔽其他所有内容并查看是否有任何内容,直接测试该位可能更为清晰:

if ((n & (1 << d)) != 0)

(可能)更容易阅读.