javaalgorithmmathdesign-patternstwos-complement

Base Negation given an inDigits


I have the following problem: Given an input in base (the input is given as an array of its digits in that base), write the negation of the number in "base's"-complement notatation in outDigits.
The "base's complement" notation of a number is a generalization of "two's complement": if we treat (-x) as an unsigned number in base and add it to x, we should get 0 (modulo base^digit-size). I cannot call other function (even Math.pow)
I keep getting an error with my tests. My code:

public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
        outDigits[0] = 1;
        for (int i = outDigits.length - 1; i >= 0; i--) {
            outDigits[i] += base - (1 + inDigits[i]);
            if (i < outDigits.length - 1) {
                outDigits[i + 1] = outDigits[i] / base;
            }
            outDigits[i] %= base;
        }
    }

I cannot find the error in my calculations, please help. my test:


------------------------------------ Negate number 365 in base 10 ------------------------------------
Test case have FAILED.
Base:    10
Input number:    [5, 6, 3]
Expected:        [5, 3, 6]
Output:          [5, 0, 0]

-------------------------------- Negate number b1010110011 in base 2 --------------------------------
Test case have FAILED.
Base:    2
Input number:    [1, 1, 0, 0, 1, 1, 0, 1, 0, 1]
Expected:        [1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
Output:          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

-------------------------------------- Negate 0x7AF0 in base 16 --------------------------------------
Test case have FAILED.
Base:    16
Input number:    [0, 15, 10, 7]
Expected:        [0, 1, 5, 8]
Output:          [0, 1, 0, 0]

Solution

  • Your problem is that you may seem to be trying to do the negation of the complement while calculating the complement and it is complicating your solution.

    You could try to simplify your solution by splitting it into two phases:

    The following method is a working version of this:

        public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
            // Compute the complement of the digits
            for (int i = outDigits.length - 1; i >= 0; i--)  
                outDigits[i] = base - (1 + inDigits[i]);
    
            // Negate the complement by adding +1 to the computed number (collection of digits)
            for (int i = 0; i < outDigits.length; i++) {  
                if (outDigits[i] == base - 1) {
                    // Max out digit. Set it to zero and try with the higher order next. 
                    outDigits[i] = 0;
                } else {
                    // Digit that has room for +1. Finally add the 1 and DONE!
                    outDigits[i]++;
                    break;
                }
            }
        }
    

    This approach is clearer, better performing and the code is self explanatory; but I added comments in the code to follow the logic used.

    Complete code on GitHub

    Hope this helps.