1
$\begingroup$

In a code, I saw someone use:

n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000

n&(-n) to remove the lsb from n ⇒ 101000 will return 100000.

This sounds magical to me. Is there any proof for these?

Thanks a lot!

$\endgroup$
2
$\begingroup$

For $n=0b101000$ we have $n-1=0b100111$, so $n \& (n-1)=0b100000$.

As to the second, then knowing $-n=\sim n+1$ we have $-n= 0b10111 +1 = 0b11000$ so $n \& (-n)= 0b101000 \& 0b11000= 0b1000$.

Addition for general proof.

  1. Let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$.Then $$n \& (-n) = 2^k$$ proof: as we know $-n=\sim n+1$. So, first step, $\sim n$, gives inversion for each bit. Hence in bits lower then $k$ we will have ones and in bit $k$ we will have zero. Now adding $1$ gives all zeros in bits lower then $k$ and in bit $k$ we again have one, but all upper bits are reversed. So $-n$ have in all bits more then $k$ reversed values with respect to $n$, which gives result.

  2. Again let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$. If we consider $n-1$, then we get zero in $k$-th bit. So $n$ and $n-1$ have different coefficient only for bit $k$. This gives, that in $n \& (n-1)$ we have all coefficients same as in $n$ besides $k$-th bit is zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.