## Puzzle #12 – Count and Add in Base -2

June 3, 2008It has really been a long time since a new puzzle appeared on the blog.

This one is a neat little puzzle that was pretty popular as an interview question. I tried to expand on it a bit, so let’s see where this goes.

The basic idea is: can you count in base -2? There is no typo here – it is **minus 2**. So far the original puzzle, now my small contribution…

Once you realize how to do this, try to build a logical circuit that performs addition *directly* (i.e. no conversions) in base -2.

Good luck!

Can you please explain the meaning of base “-2”? How will the count go in this case?

by Amit June 4, 2008 at 11:31 amThis is exactly for you do solve!! If I explain to you then there is no meaning to the question…

try to find an analogy of base 10 or base 2 and try to extrapolate to base “-2”.

This question was really given to people I know, moreover it even appeared in a book dealing with software technical interview questions.

by Nir Dahan June 4, 2008 at 12:24 pmPerverse but amusing. And the trick in an interview with this question is whether you can act as though you haven’t heard it before…

by Chuck June 4, 2008 at 1:29 pmAmit, I assume the count will go like all counts:

by kj June 4, 2008 at 5:05 pm1, 2, 3, 4, … You may require a few more bits than you are used to though.

Nir,

here is my thinking…

binary

representation in decimal

0 = 0x(-2)^0 = 0

1 = 1x(-2)^0 = 1

10 = 1x(-2)^1+0x(-2)^0= -2

11 = 1x(-2)^1+1x(-2)^0= -1

100 = 1x(-2)^2+0+0 = 4

101 = 1x(-2)^2+0+1x(-2)^0= 5

and so on…

and as for counting

the addition circuit will be same as the base 2 adder circuit.

since 101(5)+100(4)= 1001 which is 9 in base -2

and 100(4)+11(-1)=11 which is 3 in base -2

and say 101(5)+10(-2)= 11 which is 3 in base -2

Please let me know if im on the right track…

Thanks.

by Nagaraj June 5, 2008 at 6:50 amOne possibly solution to binary addition in base -2 is the following:

Let A = {a_0 a_1 … a_n-1} and B = {b_0 b_1 … b_n-1} represent the algebraic value of two numbers in base -2.

That is, A = sum_i (a_i x (-2)^i) and B = sum_i (b_i x (-2)^i) with i = 0…n-1 and, a_i and b_i in {0,1}.

Note that (a_i + b_i)x(-1)^i takes values in {0,+1,+2} if i even and {0,-1,-2} if i odd.

Also, it is obvious that, +2 = +4 + (-2) and -2 = (-4) + (+2). Note that +2 and -2 do not have a representation in the next bit position i+1, but they do in i+1 and i+2.

By extending the carry output of a conventional full-adder to bit positions i+1 and i+2 we are done.

For example, one can use two ripple adders: the first connected as usual, and the second one takes the sum and the carries of the first one.

by José June 5, 2008 at 1:31 pmNagaraj,

I think you understood it the other way around.

by Nir Dahan June 6, 2008 at 2:46 pmwe are not interested in what the sequential binary count will result in, rather we are interested in how to represent the numbers sequentially in base -2.

But I think you got the general idea…

Hi Nir,

Extending the carries does not have an efficient implementation (a second row of full-adders does not suffice! Actually, one needs n rows of full-adders (FAs) –though one less FA every subsequent row– till the extension of carries is fully processed).

A more efficient implementation can be obtained by making use of the concept of “generalized FA/HAs(half-adders)”. As before, the first row is a conventional ripple adder. The output being S = -s_0 + s_1 x 2^1 – … must be consequently inverted. A second row made of a simple incrementor (half-adders!) will do the job since -s = s_bar – 1.

by José June 20, 2008 at 6:08 amwell i can not post every thing but i can give hint we represent base2 with …(2)^3 (2)^2 (2)^1 (2)^0.(2)^-1 ….. similarly we can represent base -2 with …..(-2)^3 (-2)^2 (-2)^1 (-2)^0 ……

by sravan July 17, 2008 at 1:36 amthe number that allow for base -2 is {0,1} or {0,-1}?

by kee020041 July 31, 2008 at 6:21 amsince

base 2 using {0 to 1}

base 8 number using {0 to 7}

base 10 number using {0 to 9}

So,

base n number should used all integer start from 0 to the integer before N

then base -2 should use {0,-1}

by kee020041 July 31, 2008 at 9:29 ambase -8 should use {0,-1,-2,-3,-4,-5,-6,-7}

so, the whole series is:

let consider a 8 bit number

the order of magnitude is:

(-2)^7 (-2)^6 (-2)^5 (-2)^4 (-2)^3 (-2)^2 (-2)^1 (-2)^0

which is: (-128) (64) (-32) (16) (-8) (4) (-2) (1)

for simplification let treat ‘L’ as a symbol, that represent value of ‘-1’

then

0000000L = (-1) * ( 1) = -1

000000L0 = (-1) * ( -2) = 2

00000L00 = (-1) * ( 4) = -4

0000L000 = (-1) * ( -8) = 8

000L0000 = (-1) * ( 16) = -16

00L00000 = (-1) * ( -32) = 32

0L000000 = (-1) * ( 64) = -64

L0000000 = (-1) * (-128) = 128

Then by using convert ‘L’ to value ‘1’, the order or magnitude is just multiply with negative,

so, the order of magnitude is:

(128) (-64) (32) (-16) (8) (-4) (2) ( -1)

then, we can used value ‘1’ and ‘0’ to represent a base 2 number

i.e.

by kee020041 July 31, 2008 at 9:53 am00000110 = -4 + 2 = -2 (base 10)

00001010 = 8 + 2 = 10 (base 10)

00001100 = 8 + -4 = 4 (base 10)

continue from above, magnitude is

128 -64 32 -16 8 -4 2 -1

notice that,

T(n) + T(n+1) = – T(n) ———-[R1]

from above,

T(n) + T(n) = – T(n+1)

2 * T(n) = – T(n+1) using [R1] above

2 * T(n) = T(n+1) + T(n+2) ————-[R2]

at any bit,

by kee020041 July 31, 2008 at 10:12 am0 + 0 = 0

1 + 0 = 1

0 + 1 = 1

1 + 1 = T(n) + T(n) = 2 * T(n) using [R2]

= T(n+1) + T(n+2)

= 0, CARRY_n+1 = 1, CARRY_n+2 = 1

Number : Representation

0 : 0

1 : 001

2 : 110

3 : 111

4 : 100

.

.

.

13: 11101

Basically, the representation is b0*(-2^0)+b1*(-2^1)+b2*(-2^2)+…..+, where bn-1 bn-2….b0 is the above binary number i have given. I still wasn’t above to get a general formula for representing a number in this base 😦

by Chait April 14, 2010 at 9:42 pmit’s simple … follow the regular binary counter for even bit positions and reverse the order for odd bit positions.

Let me explain …

for a single bit counter in -2 base … it’ll be

0 –> 1 –> 0

for two bits LSB will be in increasing sequence and MSB in decreasing.

10 –> 11 –> 00 –> 01 –> 10

same for three bits 0th bit in increasing sequence 1st bit in decreasing and 2nd bit again in increasing

010 –> 011 –> 000 –> 001 –> 110 –> 111 –> 100 –> 101 –> 010

and so on …

by @nks December 17, 2010 at 6:49 pmLord ..

by saini November 23, 2012 at 3:45 pmyes saini ji …. 🙂

by @nks November 25, 2012 at 8:19 am