Checking if all bits in k between 1 to n are set

I was reading one question on the blog and the solution of t开发者_如何学JAVAhe question was to check whether 1 to n bits in 'k' are set or not.

For ex.

• k = 3 and n = 2; then "True" since 1st and 2nd bit are set in k

• k = 3 and n = 3; then "False" since 3rd bit in k is not set

The solution as provided by the author is:

    if (((1 << (n-1)) ^ (k & ((1 << n)-1))) == ((1 << (n-1))-1))
        std::cout<<"true"<<std::endl; 
    else 
        std::cout<<"false"<<std::endl; 

I am not sure what's going on here. Could someone please help me understand this?

If you draw out the binary representations on pen and paper, you'll see that (1 << (n-1)) always sets a single bit to 1 (the n-th bit), whereas (1 << n) - 1 sets the first n bits.

These are bitmasks; they're being used to manipulate certain sections of the input (k) via bitwise operations (&, | and ^).

Note

I think the example is needlessly complicated. This should be sufficient:

if ((k & ((1 << n) - 1)) == ((1 << n) - 1))
    ...

Or to make it even cleaner:

unsigned int mask = (1 << n) - 1;
if ((k & mask) == mask)
   ...

(assuming that k is of type unsigned int).