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

Question

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

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

例如：如果n = 5，它的二进制表示是101，1在第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 Language Specification on the subject 的地方，它说明了以下关于左移的内容：

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

换句话说，移位操作完全忽略除数值的低五位以外的所有内容。这意味着我们实际上并没有移动一个负数——我们移动了一个正数数量，具体数量取决于数量的最低五位~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)

这（可能）更容易阅读。

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

Need help to understand this code to find the position of 1's in a given number

java

math

bit-manipulation

bit-shift