h1

Puzzle #12 – Count and Add in Base -2

June 3, 2008

It 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!

Advertisements

17 comments

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


  2. This 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.


  3. Perverse but amusing. And the trick in an interview with this question is whether you can act as though you haven’t heard it before…


  4. Amit, I assume the count will go like all counts:
    1, 2, 3, 4, … You may require a few more bits than you are used to though.


  5. 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.


  6. One 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.


  7. Nagaraj,

    I think you understood it the other way around.
    we 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…


  8. 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.


  9. well 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 ……


  10. the number that allow for base -2 is {0,1} or {0,-1}?


  11. since
    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}
    base -8 should use {0,-1,-2,-3,-4,-5,-6,-7}


  12. 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.
    00000110 = -4 + 2 = -2 (base 10)
    00001010 = 8 + 2 = 10 (base 10)
    00001100 = 8 + -4 = 4 (base 10)


  13. 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,
    0 + 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 😦


  14. it’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 …


    • Lord ..


      • yes saini ji …. 🙂



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: