Base Negation given an inDigits

convert a number into negative base representation
negative base converter
negabinary
radix (base)
binary to negabinary
decimal to negabinary
negaternary
leetcode negative base

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]

Negative base, Gr�nwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases� But if the number-base is increased to 11, say, by adding the digit "A", then the same three positions, maximized to "AAA", can represent a number as great as 1330. We could increase the number base again and assign "B" to 11, and so on (but there is also a possible encryption between number and digit in the number-digit-numeral hierarchy).

Since the "expected" values show that index 0 is the lowest order digit, it means that for number 123₁₀ the array would be [3, 2, 1], i.e. the digits are in reverse order of what you'd expect as a human. To a computer, it makes sense that value at index i is the value that must be multiplied by baseⁱ.

That means you need the i loop to iterate up, not down, so you can track the carry-over. Otherwise you code works fine:

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

Personally, writing it like this makes more sense, especially since it doesn't rely on outDigits array to be pre-initialized to all 0's:

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

For better performance, you don't want to use % and /, so something like this might be better:

public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
    boolean carry = false;
    for (int i = 0; i < outDigits.length; i++) {
        if (carry) {
            outDigits[i] = base - inDigits[i] - 1;
        } else if (inDigits[i] != 0) {
            outDigits[i] = base - inDigits[i];
            carry = true;
        }
    }
}

Test

All 3 will give the same result:

public static void main(String[] args) {
    test(10, 5,6,3);
    test(2,  1,1,0,0,1,1,0,1,0,1);
    test(16, 0,15,10,7);
    test(8,  0,0,0); // 0 -> 0 (000)
    test(8,  1,0,0); // 1 -> -1 (777)
    test(8,  7,7,3); // 255 -> -255 (104)
    test(8,  0,0,4); // -256 -> -256 (004)
}

static void test(int base, int... inDigits) {
    int[] outDigits = new int[inDigits.length];
    baseNegate(base, inDigits, outDigits);
    System.out.printf("%d: %s -> %s%n", base, Arrays.toString(inDigits),
                                        Arrays.toString(outDigits));
}

Output

10: [5, 6, 3] -> [5, 3, 6]
2: [1, 1, 0, 0, 1, 1, 0, 1, 0, 1] -> [1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
16: [0, 15, 10, 7] -> [0, 1, 5, 8]
8: [0, 0, 0] -> [0, 0, 0]
8: [1, 0, 0] -> [7, 7, 7]
8: [7, 7, 3] -> [1, 0, 4]
8: [0, 0, 4] -> [0, 0, 4]

Third Base, (You can build perfectly good numbers on a negative or an irrational base, and In other words, if r is the radix and w is the width in digits, we want to minimize rw Given this labeling, the first middle third to be erased consists of those points� 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.

I think there's a problem around here:

if (i < outDigits.length - 1) {
    outDigits[i + 1] = outDigits[i] / base;
}

Let's say you're using base 10. Since a digit can only be 0 through 9, dividing by 10 would mean the result of this calculation is always 0. I don't think you intended this.

Basic Number Properties: Associative, Commutative, and , There are three basic properties of numbers, and your textbook will probably have just a little section on these In numbers, this means, for example, that 2(3 + 4) = 2�3 + 2�4. as the subtraction of a positive number ("x – 2") or else as the addition of a negative number ("x + (–2)"). In the 2(3x) : original (given) statement. 2 Base Negation given an inDigits Nov 28 '19. 2 Increasing Subsequence Recursive Java Dec 12 '18. 2 The Birthday Problem - at least 2 out of N Oct 24 '18. 1 Parity

How to Add, Subtract, Multiply, and Divide Positive and Negative , Zero, the dividing point, is neither positive nor negative. Want to learn more? Take an online course in Basic Math. When we move to the right on the number line, we increase in numbers. We defined this as addition Sea level is given as 0. Note that the transformation above has little to do with the presence of a quantifier; it's simply an application of double negation to a quantified statement. Note also that what we ended with can equivalently be expressed as follows: $$\forall x (\lnot p(x)) \equiv \lnot \exists x(p(x))$$

1877: Anti-Duhring, This re-establishes individual property, but on the basis of the acquisitions of the a class always increasing in numbers, and disciplined, united, organised by the gave them the same cramps as Herr D�hring gets from the negation of the � Negation Sometimes in mathematics it's important to determine what the opposite of a given mathematical statement is. This is usually referred to as "negating" a statement. One thing to keep in mind is that if a statement is true, then its negation is false (and if a statement is false, then its negation is true).

Negative Integer Number Base, The base − r -r −r expansion of a a a is then given by the string� The Negation Rule: In English, in order to claim that something is not true, you form a negative sentence by adding the word not after the first auxiliary verb in the positive sentence. If there is

Comments
  • You seem to have skipped a step, or at least not shown it. You've described what needs to be done. The next step is to define an algorithm, and reason why you think it works. Then, only after you've convinced yourself it's correct, you should reduce it to code. It will help us if you can add a high-level description of the algorithm with enough detail to evaluate its correctness and check that your code implements it.
  • You can do it on the fly. OP was 99% there, was just iterating the wrong way. See my answer.