janmr blog

The nth Bit of a Negative Number

Assume a positive integer xx is given and we wish to get the value of the nnth bit of the number's two's complement (written here as x-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 nnth 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=(...x2x1x0)2x = (... x_2 x_1 x_0)_2 and assume that the number has kk trailing zeros, that is, xk=1x_k = 1 and xk1=...=x1=x0=0x_{k-1}=...=x_1=x_0=0. So it has the appearance

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

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

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

and then add one to obtain

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

Now we see that

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

where kk the the number of trailing zeros of the number x=(...x2x1x0)2x = (... 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