ndatta's blog

number in -2 (minus two) bases
By ndatta, history, 9 years ago, In English

Given a number in base -2 in binary form. return negative of that number in base -2 in binary form. Given [1,0,0,1,1,1] => return [1,1,0,1,0,1,1]. [1,0,0,1,1,1] = -23 (from left) , neg(-23) = 23 in base -2, 23 is [1,1,0,1,0,1,1]. Length of the given array <= 10^5

Any idea? Thanks in advance.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ndatta (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

One idea would be to look at the representations of a few small numbers, for example, +1 and -1, +2 and -2, ..., +10 and -10. You may be able to better understand what is going on just by looking at them.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. I tried but I found out only that positive numbers are of odd length and negative numbers are of even length. That's all :( !!

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That is a problem I solved during pre-interview once. The key points to the solution:

  1. Assuming you have this kind of bit representation of arbitrary X if you shift all bits to the left (towards greater powers) you will get  - 2·X.

  2. If you add bit-by-bit  - 2·X and X you will get  - X which is what you're looking for. But summing bits in naive way might produce some bit equal to 2 which is illegal.

  3. You need to get rid of number 2 in bit representation. So you need some rules to eliminate them. Below I show you two rules which are enough. I'll show them as string where characters to the right correspond to higher order bits.

a. 21 -> 00

b 20 -> 011

So iterate lower to higher bits and apply these two substitution rules when necessary.

→ Reply