Bitwise n&-n

I was solving a problem on codeforces that required me to find a vallue  2k where k is the position of the first one in the binary representation of n.
I was confused initially, but then I found out that this exact quanti5ty can be found out by ANDing n with it negative.
But how?

-n can be written as ~n + 1, where ~n denotes the complement of n. If we add 1 to the complement of n, we get a number same upto the first 1, and inverted after that! For example,

If we take n=1001110, then
-n= 0110010         (as ~n = 0110001, and ~n+1 = 0110010)
————————
n&-n = 0000010

That’s exactly what I’m saying here. If n=4, then n&-n = 4, which is 2 raised to the power the position of the first set bit.
Let’s take one more example for n = 12

n = 1100
-n= 0100
——————————
12 & -12 = 0100  = 4.

This can also be used to check if a number is perfect square or not.

If (n== n&-n) condition is satisfied, then the number n is a perfect sqaure, because only one bit will be set in the binary representation of n, making n&-m yield n itself.

Just wanted to write this, so I remember this. And also because I couldn’t find too many links explaining it.

http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2/600306#600306

http://stackoverflow.com/questions/7405438/why-if-n-n-n-then-n-is-a-power-of-2

~jigsaw

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s