# janmr blog

## The nth Bit of a Negative Number January 09, 2021

Assume a positive integer $x$ is given and we wish to get the value of the $n$th bit of the number's two's complement (written here as $-x$). Now if a fixed number of bits is used to represent the number, say 32 or 64, the two's complement can be computed explicitly and the $n$th bit can be found directly. But if we work with arbitrary precision then any two's complement representation has infinitely many 1s at the left.

Let some positive number have the binary representation $x = (... x_2 x_1 x_0)_2$ and assume that the number has $k$ trailing zeros, that is, $x_k = 1$ and $x_{k-1}=...=x_1=x_0=0$. So it has the appearance

$x = (... x_{k+2} x_{k+1} 1 0 ... 0)_2.$

Now to obtain the two's complement, we must first negate each bit,

$\overline{x} = (... \overline{x}_{k+2} \overline{x}_{k+1} 0 1 ... 1)_2$

and then add one to obtain

$-x = \overline{x} + 1 = (... \overline{x}_{k+2} \overline{x}_{k+1} 1 0 ... 0)_2.$

Now we see that

$\text{the nth bit of -x} = \begin{cases} x_n & \text{for n \leq k,} \\ \overline{x}_n & \text{for n > k} \end{cases}$

where $k$ the the number of trailing zeros of the number $x = (... x_2 x_1 x_0)_2$.

Commenting is not possible for this post, but feel free to leave a question, correction or any comment by using the contact page