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.
-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
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.