2

I've been trying to wrap my head around this one problem for the last couple of days, and I can't figure out a way to solve it. So, here it goes:

Given the base 4(that is 0, 1, 2, 3 as digits for a number), find the excess (-1) in base 4 representation of any negative or positive integer number. examples: -6 = (-1)22 conversely, (-1)22 in excess (-1) of base 4 = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 8 - 16 = 10 - 16 = -6 in base 10

27 = 2(-1)(-1) conversely, 2(-1)(-1) = (-1) * 4^0 + (-1) * 4^1 + 2 * 4^2 = -1 - 4 + 32 = 27

I did come up with a few algorithms for positive numbers, but none of them hold true for all negative numbers, so into the trash they went.

Can anyone give me some kind of clue here? Thanks!

----------------

Edit: I'm going to try to rephrase this question in such a way that it does not raise any confusions.

Consider the radix obtained by subtracting 1 from every digit, called the excess-(-1) of base 4. In this radix, any number can be represented using the digits -1, 0, 1, 2. So, the problem asks for an algorithm that gets as an input any integer number, and gives as output the representation of that given number.

Examples:

decimal -6 = -1 2 2 for the excess-(-1) of base 4.

To verify this, we take the representation -1 -1 2 and transform it to a decimal number, start from the right-most digit and use the generic base n to base 10 algorithm, like so:

number = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 4 - 16 = -6

2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 4 - 16 = -6

Community
  • 1
  • 1
ijustpostedsomethingdumb
  • 81
  • 9
  • What does mean "(-1)22" "2(-1)(-1)" ? Can you do better example, more readable ? I think you need to find a algorithm that work with all base. (maybe not 1) – Stargateur Nov 18 '16 at 13:56
  • (-1)22 is the representation in excess -1 of base 4 for the decimal number -6. Imagine this as a custom radix that has -1, 0, 1, 2 as digits. So the decimal number -6 is represented as (-1) 2 2 in this custom radix. The parantheses are there just to improve readability. – ijustpostedsomethingdumb Nov 18 '16 at 14:03
  • It's hard to understand if you jump of base in a(10) = b(6). Maybe [this](http://stackoverflow.com/questions/18074057/how-do-you-calculate-a-decimal-number-to-8-bit-excess-binary) help you or [this](https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/bias.html). I don't understand what is your purpose ( I don't know what is a excess (-1) ), why not write -6 in decimal give -12 in base 4 ? – Stargateur Nov 18 '16 at 14:21
  • Thanks for the tip, but I have already read through those a few times, they didn't help me. For example, computing the excess of -1 in base 4 for the decimal number -6 using the ideas I got from those links outputs result = -1 -1 However, I know for sure that decimal -6 = -1 2 2 – ijustpostedsomethingdumb Nov 18 '16 at 14:59

1 Answers1

1

I don't know if "quaterit" is the correct word for the radix in this representation, but I'm going to use it anyway.

Since you say you already have an algorithm for positive numbers, I'll try to take a negative number as an input and write something that uses what you already have. The code below doesn't quite work, but I'll explain why at the end.

int[] BaseFourExcessForNegativeNumbers(int x) {
    int powerOfFour = 1;
    while (-powerOfFour > x) {
        powerOfFour *= 4;
    }
    int firstQuaterit = -1;
    int remainder = x + powerOfFour;
    int[] otherQuaterits;
    if (remainder >= 0) {
        otherQuaterits = BaseFourExcessForPositiveNumbers(remainder);
    } else {
        otherQuaterits = BaseFourExcessForNegativeNumbers(remainder);
    }
    int[] result = new int[otherQuaterits.Length + 1];
    result[0] = firstQuaterit;
    for (int index = 0; index < otherQuaterits.Length; ++index) {
        result[index + 1] = otherQuaterits[index];
    }
    return result;
}

The idea here is that every negative number x will start with a (-1) in this representation. If that (-1) is in the 4^n position, we want to find out how to represent x - (-1)*4^n to see how to represent the rest of the number.

The reason the code I wrote won't work is that it doesn't take into consideration the possibility that the second quaterit is a 0. If that happens, the array my code will produce will be missing that 0. In fact, if BaseFourExcessForPositiveNumbers is written in the same way, the resulting array will be missing every 0, but will otherwise be correct. A workaround is to keep track of which place the first quaterit takes, and then make the array that size, and fill it from the back to the front.

Pi Fisher
  • 260
  • 1
  • 11