Extracting rightmost N bits of an integer

Question

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)

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.

Answer 1

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.

Answer 2

for exaple: 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

Answer 3

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.