ThmDex – An index of mathematical definitions, results, and conjectures.

Result R5720 on D6263: Integer base-2 representation

Negative of base-2 integer iff bits negated plus one

Formulation 0

Let $r_{N - 1}, \, \ldots, r_1, r_0$ be a D6263: Integer base-2 representation such that

(i)	\begin{equation} a = - r_{N - 1} 2^{N - 1} + \sum_{n = 0}^{N - 2} r_n 2^n \end{equation}

Then \begin{equation} - a = 1 - (1 - r_{N - 1}) 2^{N - 1} + \sum_{n = 0}^{N - 2} (1 - r_n) 2^n \end{equation}

Remarks

▶

Remark 0 (The standard algorithm for finding the base-2 integer of an additive inverse)

This result yields a simple algorithm for finding the base-2 representation for the additive inverse of an integer. If $r_{N - 1}, \, \ldots, \, r_1, r_0$ is a binary representation for an integer $a$, then flipping the digits to $(1 - r_{N - 1}), \, \ldots, \, (1 - r_1), (1 - r_0)$ and adding $1$ yields a binary representation for $-a$.

Proofs

Proof 0

Let $r_{N - 1}, \, \ldots, r_1, r_0$ be a D6263: Integer base-2 representation such that

(i)	\begin{equation} a = - r_{N - 1} 2^{N - 1} + \sum_{n = 0}^{N - 2} r_n 2^n \end{equation}

Using result R5721: Base-2 integer representation for minus one, we have \begin{equation} \begin{split} - (a) = 1 - (a) + (- 1) & = 1 - \left(- r_{N - 1} 2^{N - 1} + \sum_{n = 0}^{N - 2} r_n 2^n \right) + \left( - 2^{N - 1} + \sum_{n = 0}^{N - 2} 2^n \right) \\ & = 1 + \left(r_{N - 1} 2^{N - 1} + \sum_{n = 0}^{N - 2} - r_n 2^n \right) + \left( - 2^{N - 1} + \sum_{n = 0}^{N - 2} 2^n \right) \\ & = 1 + (r_{N - 1} - 1) 2^{N - 1} + \sum_{n = 0}^{N - 2} (1 - r_n) 2^n \\ & = 1 - (1 - r_{N - 1}) 2^{N - 1} + \sum_{n = 0}^{N - 2} (1 - r_n) 2^n \\ \end{split} \end{equation} $\square$