Extracting rightmost N bits of an integer

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)-开发者_JS百科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.

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

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

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

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

The equality holds if and only if the last N bits are all 1. Thus the expression checks if K ends with N ones.

For example: 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

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.

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:

            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.

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.

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.

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.

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:

$tests = <>;
for (1..$tests) {
    ($n, $k) = split / /, <>;
    $m = 1 << $n - 1;
    printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF';
}

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.

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.