在 Java 中利用按位 & 将数字检测为 2 的幂
Utilizing bitwise & to detect a number as a power of 2 in Java
在处理 Hackerrank 上的一个问题时，我在提供给我们的代码中看到了这段代码：
(num&num-1)==0 我的问题是为什么这会告诉我变量 num 是否是 2 的幂？
我注意到代码运行良好。我认为正在发生的是按位 & 运算符用于将变量 num 转换为二进制，然后从中减去 1 我也相信 1 正在转换为二进制？我不太确定到底发生了什么，但是对于像 8 这样的数字，结果总是等于 0 而对于像 9 这样的数字，结果则不是。有人可以解释一下使这段代码起作用的幕后情况吗？
让我们看看二进制表示。 2 的幂是 1 后跟一系列 0（例如，2 在二进制中是 10，4 是 100，8 是 1000，等等）。如果从中减去 1，您将得到一系列与原始数字中的 0 相匹配的 1。如果然后 & 在它们之间，每个 1 将与一个 0 匹配，结果将为 0。对于任何不是 2 的幂的数字，您将在 num 和 num-1，因此当你 & 他们时得到一个非零结果。
如果将2的幂转换为二进制表示，则其剩余位置恰好包含一个1和0，例如（以 8 位表示）：
2^4 = 0001 0000
从这样的数字中减一会将 1 位设置为零，并将其后面的所有位设置为一：
2^4 - 1 = 0000 1111
这意味着，对于 2 的幂，在这两种情况下均未设置任何位，并且 x & (x - 1) 为零。
如果不是2的幂的数被翻译成二进制表示，它至少包含两个1，例如（以 8 位表示）：
12 = 0000 1100
从这个数字中减一会将最低位的 1 设置为 0，并将其后面的所有 0 设置为 1：
12 - 1 = 0000 1011
但由于这个数字至少包含两位，所以至少还有一位没有被修改。所以，在x & (x - 1)中，至少设置了一位，且该数不等于0。
不过，这在一种情况下不起作用，因为它会将 0 检测为 2 的幂（因为 0 & -1 == 0 为真）。
the bitwise & operator is used to convert the variable num to binary and then 1 is subtracted from it and I also believe the 1 is being converted to binary?
没有。没有转换为二进制发生。数字 是 二进制。这就是所有计算机可以使用的：二进制数。
在二进制中，8是1000。如果你减去 1，你会得到 7：0111。所以，当你对这两个数字使用按位和时，你会得到
1000
& 0111
------
= 0000
对于非 2 的幂，数字中的 1 总是多于一个，减去 1 将保留最左边的 1。例如，对于 9，您将有
1001
& 1000
------
= 1000
9表示为1001
8表示为1000
现在 9&8 将是
1001 & 1000 即 1000
让我们用 8
试试这个
8表示为1000
7表示为0111
现在 8&7 将是
1000 & 0111 即 0000
对于odd个数，至少会有one bit个不抵消。而对于 even 个数字，它们相互抵消。
要了解 logical AND (&)，请查看：https://en.wikipedia.org/wiki/Truth_table#Logical_conjunction_(AND)
在处理 Hackerrank 上的一个问题时，我在提供给我们的代码中看到了这段代码：
(num&num-1)==0 我的问题是为什么这会告诉我变量 num 是否是 2 的幂？
我注意到代码运行良好。我认为正在发生的是按位 & 运算符用于将变量 num 转换为二进制，然后从中减去 1 我也相信 1 正在转换为二进制？我不太确定到底发生了什么，但是对于像 8 这样的数字，结果总是等于 0 而对于像 9 这样的数字，结果则不是。有人可以解释一下使这段代码起作用的幕后情况吗？
让我们看看二进制表示。 2 的幂是 1 后跟一系列 0（例如，2 在二进制中是 10，4 是 100，8 是 1000，等等）。如果从中减去 1，您将得到一系列与原始数字中的 0 相匹配的 1。如果然后 & 在它们之间，每个 1 将与一个 0 匹配，结果将为 0。对于任何不是 2 的幂的数字，您将在 num 和 num-1，因此当你 & 他们时得到一个非零结果。
如果将2的幂转换为二进制表示，则其剩余位置恰好包含一个1和0，例如（以 8 位表示）：
2^4 = 0001 0000
从这样的数字中减一会将 1 位设置为零，并将其后面的所有位设置为一：
2^4 - 1 = 0000 1111
这意味着，对于 2 的幂，在这两种情况下均未设置任何位，并且 x & (x - 1) 为零。
如果不是2的幂的数被翻译成二进制表示，它至少包含两个1，例如（以 8 位表示）：
12 = 0000 1100
从这个数字中减一会将最低位的 1 设置为 0，并将其后面的所有 0 设置为 1：
12 - 1 = 0000 1011
但由于这个数字至少包含两位，所以至少还有一位没有被修改。所以，在x & (x - 1)中，至少设置了一位，且该数不等于0。
不过，这在一种情况下不起作用，因为它会将 0 检测为 2 的幂（因为 0 & -1 == 0 为真）。
the bitwise & operator is used to convert the variable num to binary and then 1 is subtracted from it and I also believe the 1 is being converted to binary?
没有。没有转换为二进制发生。数字 是 二进制。这就是所有计算机可以使用的：二进制数。
在二进制中，8是1000。如果你减去 1，你会得到 7：0111。所以，当你对这两个数字使用按位和时，你会得到
1000
& 0111
------
= 0000
对于非 2 的幂，数字中的 1 总是多于一个，减去 1 将保留最左边的 1。例如，对于 9，您将有
1001
& 1000
------
= 1000
9表示为1001
8表示为1000
现在 9&8 将是
1001 & 1000 即 1000
让我们用 8
8表示为1000
7表示为0111
现在 8&7 将是
1000 & 0111 即 0000
对于odd个数，至少会有one bit个不抵消。而对于 even 个数字，它们相互抵消。
要了解 logical AND (&)，请查看：https://en.wikipedia.org/wiki/Truth_table#Logical_conjunction_(AND)