Title: Theory / Unimportant / CS / Algo / Hacker's delight{ / 12 Unusual bases / Base -2
Tags: récupéré

Name: base -2
Definition: A sequence of bit \(a_n\dots a_0\) encodes \(\sum_{i=0}^n a_i(-2)^i\)
Page: 223
Chapter: 12
Section: 1
Name2: negabinary basis

Question: The numbers which can be represented with \(n\) bits in basis \(-2\)
Answer: \(\left[-\frac{2^{n+1}-2}3,\frac{2^n-1}3\right]\) for \(n\) even
\(\left[-\frac{2^{n}-2}3,\frac{2^{n+1}-1}3\right]\) for \(n\) odd
Page: 224
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Kind: eq

Question: \(1+1\) equals
Answer: \(110\)
Page: 225
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Context: Basis -2

Question: \(11+1\) equals
Answer: \(0\)
Page: 225
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Context: Base -2

Question: \(1+1+1\) equals
Answer: \(111\)
Page: 225
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Context: base -2

Question: \(0-1\) equals
Answer: \(11\)
Page: 225
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Context: Base -2

Question: \(11-1\) equals
Answer: \(10\)
Page: 225
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Context: base -2

Question: The remaining of the division of \(n\) by \(-2\)
Answer: equals \(n\mod 2\)
Page: 223
Chapter: 12
Section: 2
Variables: \(n\) an integer

Page: 223
Section: 2
Notation: The representation of \(n\) in base -2
Variables: \(n\) an integer
Chapter: 12
Example: By induction:
if \(n=0\), the empty string otherwise, the remainder \(r\) of the division of \(n\) by \(-2\) followed by the representation of \(\frac{n-r}2\)