java 提取整数最右边的 N 位
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2798191/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Extracting rightmost N bits of an integer
提问by srandpersonia
In the yester Code Jam Qualification round http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0, there was a problem called Snapper Chain. From the contest analysis I came to know the problem requires bit twiddling stuff like extracting the rightmost N bits of an integer and checking if they all are 1. I saw a contestant's(Eireksten) code which performed the said operation like below:
在昨天的 Code Jam 资格赛http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0 中，出现了一个名为 Snapper Chain 的问题。从比赛分析中我开始知道这个问题需要一些复杂的东西，比如提取一个整数最右边的 N 位并检查它们是否都是 1。我看到了一个参赛者（Eireksten）的代码，它执行了如下所述的操作：
(((K&(1<<N)-1))==(1<<N)-1)
I couldn't understand how this works. What is the use of -1 there in the comparison?. If somebody can explain this, it would be very much useful for us rookies. Also, Any tips on identifying this sort of problems would be much appreciated. I used a naive algorithm to solve this problem and ended up solving only the smaller data set.(It took heck of a time to compile the larger data set which is required to be submitted within 8 minutes.). Thanks in advance.
我无法理解这是如何工作的。在比较中 -1 有什么用？如果有人能解释一下，对我们菜鸟会很有帮助。此外，任何有关识别此类问题的提示将不胜感激。我使用了一个天真的算法来解决这个问题，最终只解决了较小的数据集。（编译需要在 8 分钟内提交的较大数据集花费了大量时间。）。提前致谢。
回答by kennytm
Let's use N=3 as an example. In binary, 1<<3 == 0b1000. So 1<<3 - 1 == 0b111.
我们以 N=3 为例。在二进制中，1<<3 == 0b1000. 所以1<<3 - 1 == 0b111。
In general, 1<<N - 1creates a number with N ones in binary form.
通常，1<<N - 1以二进制形式创建一个具有 N 个 1 的数字。
Let R = 1<<N-1. Then the expression becomes (K&R) == R. The K&Rwill extract the last N bits, for example:
让R = 1<<N-1. 然后表达式变为(K&R) == R。所述K&R将提取的最后N个比特，例如：
101001010
& 111
————————————
000000010
(Recall that the bitwise-AND will return 1 in a digit, if and only if both operands have a 1 in that digit.)
（回想一下，按位与将在一个数字中返回 1，当且仅当两个操作数在该数字中都为 1。）
The equality holds if and only if the last N bits are all 1. Thus the expression checks if K ends with N ones.
当且仅当最后 N 位全为 1 时，等式成立。因此，表达式检查 K 是否以 N 位结束。
回答by Nikel
For example: N=3, K=101010
例如：N=3，K=101010
1. (1<<N) = 001000 (shift function)
2. (1<<N)-1 = 000111 (http://en.wikipedia.org/wiki/Two's_complement)
3. K&(1<<N)-1 = 0000010 (Bitmask)
4. K&(1<<N)-1 == (1<<N)-1) = (0000010 == 000111) = FALSE
回答by Anonymous
I was working through the Snapper Chain problem and came here looking for an explanation on how the bit twiddling algorithm I came across in the solutions worked. I found some good info but it still took me a good while to figure it out for myself, being a bitwise noob.
我正在解决 Snapper Chain 问题，并来到这里寻找有关我在解决方案中遇到的 bit twiddling 算法如何工作的解释。我找到了一些不错的信息，但作为一个小白，我还是花了很长时间才弄明白。
Here's my attempt at explaining the algorithm and how to come up with it. If we enumerate all the possible power and ON/OFF states for each snapper in a chain, we see a pattern. Given the test case N=3, K=7 (3 snappers, 7 snaps), we show the power and ON/OFF states for each snapper for every kth snap:
这是我试图解释算法以及如何提出它的尝试。如果我们为链中的每个 snapper 枚举所有可能的电源和 ON/OFF 状态，我们就会看到一个模式。给定测试用例 N=3，K=7（3 个 snapper，7 个 snap），我们显示每个 snapper 的电源和 ON/OFF 状态对于每个第 k 个 snap：
1 2 3
0b:1 1 1.1 1.0 0.0 -> ON for n=1
0b:10 2 1.0 0.1 0.0
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2
0b:100 4 1.0 0.0 1.0
0b:101 5 1.1 1.0 1.0 -> ON for n=1
0b:110 6 1.0 0.1 0.1
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3
The lightbulb is on when all snappers are on and receiving power, or when we have a kth snap resulting in n 1s. Even more simply, the bulb is on when all of the snappers are ON, since they all must be receiving power to be ON (and hence the bulb). This means for every k snaps, we need n 1s.
当所有快照器都打开并接收电源时，或者当我们有第 k 个快照导致 n 1s 时，灯泡就会亮起。更简单的是，当所有的鲷鱼都打开时，灯泡就会打开，因为它们都必须通电才能打开（以及灯泡）。这意味着对于每 k 个快照，我们需要 n 个 1。
Further, you can note that k is all binary 1s not only for k=7 that satisfies n=3, but for k=3 that satisifes n=2 and k=1 that satisifes n=1. Further, for n = 1 or 2 we see that every number of snaps that turns the bulb on, the last n digits of k are always 1. We can attempt to generalize that all ks that satisfy n snappers will be a binary number ending in n digits of 1.
此外，您可以注意到 k 都是二进制 1，不仅对于满足 n=3 的 k=7，而且对于满足 n=2 的 k=3 和满足 n=1 的 k=1。此外，对于 n = 1 或 2，我们看到打开灯泡的每个快照数，k 的最后 n 位数字始终为 1。我们可以尝试概括满足 n 个快照程序的所有 ks 将是一个以n 位 1。
We can use the expression noted by an earlier poster than 1 << n - 1 always gives us n binary digits of 1, or in this case, 1 << 3 - 1 = 0b111. If we treat our chain of n snappers as a binary number where each digit represents on/off, and we want n digits of one, this gives us our representation.
我们可以使用之前发布者提到的表达式 1 << n - 1 总是给我们 n 个二进制数字 1，或者在这种情况下， 1 << 3 - 1 = 0b111。如果我们将我们的 n 个 snapper 链视为一个二进制数，其中每个数字代表开/关，并且我们想要 n 位数字，这给了我们我们的表示。
Now we want to find those cases where 1 << n - 1 is equal to some k that ends in n binary digits of 1, which we do by performing a bitwise-and: k & (1 << n - 1) to get the last n digits of k, and then comparing that to 1 << n - 1.
现在我们想要找到那些 1 << n - 1 等于某个 k 以 n 个二进制数字 1 结尾的情况，我们通过执行按位与：k & (1 << n - 1) 来得到k 的最后 n 位，然后将其与 1 << n - 1 进行比较。
I suppose this type of thinking comes more naturally after working with these types of problems a lot, but it's still intimidating to me and I doubt I would ever have come up with such a solution by myself!
我想这种类型的想法在处理了很多这些类型的问题后会更自然地出现，但它仍然让我感到害怕，我怀疑我自己是否会想出这样的解决方案！
Here's my solution in perl:
这是我在 perl 中的解决方案：
$tests = <>;
for (1..$tests) {
($n, $k) = split / /, <>;
$m = 1 << $n - 1;
printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF';
}
回答by monn
I think we can recognize this kind of problem by calculating the answer by hand first, for some series of N (for example 1,2,3,..). After that, we will recognize the state change and then write a function to automate the process (first function). Run the program for some inputs, and notice the pattern.
我认为我们可以通过首先手工计算答案来识别这类问题，对于一些 N 系列（例如 1,2,3,..）。之后，我们将识别状态变化，然后编写一个函数来自动化该过程（第一个函数）。为一些输入运行程序，并注意模式。
When we get the pattern, write the function representing the pattern (second function), and compare the output of the first function and the second function.
当我们得到模式时，编写表示模式的函数（第二个函数），并比较第一个函数和第二个函数的输出。
For the Code Jam case, we can run both function against the small dataset, and verify the output. If it is identical, we have a high probability that the second function can solve the large dataset in time.
对于 Code Jam 案例，我们可以针对小数据集运行这两个函数，并验证输出。如果相同，我们很有可能第二个函数可以及时解决大数据集。
