提取整数的最右边的N位 [英] Extracting rightmost N bits of an integer

问题描述

在昨code果酱资格赛<一个href=\"http://$c$c.google.com/$c$cjam/contest/dashboard?c=433101#s=a&a=0\">http://$c$c.google.com/$c$cjam/contest/dashboard?c=433101#s=a&a=0 ，有一个叫做鲷鱼链问题。从比赛分析，我才知道的问题，需要有点摆弄像提取一个整数的最右边的N位和检查的东西，如果他们都是我看见一个选手的（Eireksten）code这执行上述操作如下图所示：

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:

(((K&(1<<N)-1))==(1<<N)-1)

我不明白这是如何工作。这是在比较中使用的-1存在？如果有人可以解释这一点，那将是对我们新手非常有用的。此外，在识别这类问题的任何提示将是非常美联社preciated。我用了一个天真的算法来解决这个问题，最终解决只有较小的数据集。（它花了一段时间来编译这是需要在8分钟之内提交的更大的数据集赫克）。先谢谢了。

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.

推荐答案

让我们用N = 3为例。在二进制， 1 LT; 3; == 0b1000 。因此， 1 LT; 3; - 1 == 0b111

Let's use N=3 as an example. In binary, 1<<3 == 0b1000. So 1<<3 - 1 == 0b111.

在一般情况下， 1 LT;＆LT; N - 1 创建了n个二进制形式的数

In general, 1<<N - 1 creates a number with N ones in binary form.

让 R = 1＆LT;＆LT; N-1 。然后前pression变得（K＆安培; R）== - [R 。在 K＆安培; R 将提取的最后N位，例如：

Let R = 1<<N-1. Then the expression becomes (K&R) == R. The K&R will extract the last N bits, for example:

     101001010
  &        111
  ———————————— 
     000000010

（回想一下，按位与将在一个数字返回1，当且仅当两个操作数的该位具有1）

(Recall that the bitwise-AND will return 1 in a digit, if and only if both operands have a 1 in that digit.)

等号成立当且仅当最后N位都是1。因此除权pression检查，如果K的n个结束。

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位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！