division by 2 in Binary Signed digit (Redundant Binary representation)

Question

How can I do division by 2 in Binary Signed digit (Redundant Binary representation) ? Shifting won't work right ?

Answer 1

A redundant binary representation is just an expression of the form:

\sum_{i=0}^n d_i 2^n

where the d_i's are drawn from a larger set than just {0,1}.

Dividing by two or shifting right takes that to

\sum_{i=0}^{n-1} d_{i+1} 2^n + f(d_0)

The trick comes in how to deal with adjusting for the redundant representation for d_0.

If your RBR has digits the form {0,1,2} and has a 2 for the least significant digit you will then have to add 1 to the result to compensate, so f(0) = 0, f(1) = 0, f(2) = 1 should work.

• 4 = 12_base2, so 12_base2 >> 1 = 1 + f(2) = 1 + 1 = 2_base2 = 2 as expected.
• 6 = 102_base2, so 102_base2 >> 1 = 10_base2 + f(2) = 11_base2 = 3

You can get something similar for signed redundant binary representations (i.e. with d_i in {-1,0,1}) by setting f(-1) = -1.

• 1 = 1(-1)_base2, so 1(-1)_base2 >> 1 = 1 + f(-1) = 1 - 1 = 0

So ultimately the naive approach of just shifting does work, you just need a fudge factor to account for any redundant encoding of the shifted digits.

If your chosen RBR includes more options, you'll need to adjust the fudge factor accordingly.