Finding a nonzero integer x where x == -x?

Question

In a course on algorithms and data structures at my university, I received this question:

Which integer has the same bit-pattern as his negative value?

Means: x == -x

I know that 0 works, but I suspect that the instructor was looking for some other number x. What x is it? How would you find it?

Answer 1

Integer.MIN_VALUE and Long.MIN_VALUE have no equivalent positive value and when you take the negative value of these, you get the same value.

Negative is the same as flipping all the bits and adding one. i.e.

-x = ~x + 1

So -0x80000000 = 0x7fffffff + 1 = 0x8000000

Note: Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE which is negative. This is outlined in the javadoc for this method.

Technically there are many answers and types

byte x = 0;
short x = 0;
char x = 0;
int x = 0;
int x = Integer.MIN_VALUE;
float x = 0.0f;
float x = -0.0f;
long x = 0;
long x = Long.MIN_VALUE;
double x = 0.0;
double x = -0.0;
Byte x = 0;
Short x = 0;
Character x = 0;
Integer x = 0;
Integer x = Integer.MIN_VALUE;
Float x = 0.0f;
Float x = -0.0f;
Long x = 0L;
Long x = Long.MIN_VALUE;
Double x = 0.0;
Double x = -0.0;

---

A similar Java Puzzler is; when is the following expression true.

x != x + 0

---

EDIT: Floating point has both +0.0 and -0.0. A such you might consider -0.0 a different value to 0.0 although it is the case that -0.0 == -(-0.0)

Note: Double.compare(0.0, -0.0) > 0 Note:

Answer 2

Suppose that you take the lowest possible representable number in signed two's-complement format. Let's say this number (call it x) has bit pattern 100000...0, for example. To compute -x, you first flip all the bits to get 01111...1, then add one to it. This causes a large ripple carry that results in the number 1000....0 again, which is the number that you started with. Thus you would have that x == -x. In the case of Java ints, this value is Integer.MIN_VALUE, which is -2³¹.

You can actually figure this out mathematically. Since all numbers in signed two's-complement format are represented modulo some power of two (say, 2^d), then the statement

x == -x

Really means

x == -x (mod 2^d)

This means that

2x == 0 (mod 2^d)

Therefore, the solutions to this problem are the set of all numbers x where 2x is 0 mod 2^d. These are numbers of the form k × 2^d for any integer k. Only two of these values can be represented in signed two's-complement format with d + 1 bits, namely, 0 and -2^d. Therefore, the minimum possible negative number will always compare equal to its negative value.

Hope this helps!

Answer 3

For an 8 bit integer: 1000 0000 signed this is -128 while unsigned this is 128

Answer 4

To look at this another way: All signed primitive integer types represent integers in the range

-2^N-1 to 2^N-1-1

(inclusive), where N is the number of bits. Whenever any mathematical integer operation is performed, if the mathematical result is some number Z that is outside that range ("overflow"), then the actual result will be R = Z + 2^N * k, where k is some positive or negative integer chosen so that R will be in the range -2^N-1 to 2^N-1 - 1. So say x = -2^N-1, and we compute -x. The mathematical result is Z = 2^N-1, but that's out of range because Z > 2^N-1-1. So to get it in range, we need to add 2^N * k for some k, and k must be -1. Thus the actual result is R = 2^N-1 + (2^N)*(-1) = 2^N-1 - 2^N = -2^N-1, which is the original value of x. So that's a value that makes x == -x.

Java has only signed integer types, but in languages that have unsigned types, the range for unsigned types is 0 to 2^N-1, inclusive. But everything else applies in the same way.

Answer 5

The question, as stated, is ambiguous.

0 is of course the obvious solution, and as others have discussed there are no other solutions in Java (which is how the question is tagged).

In C, for any signed integer type, the minimum value of the given type may be a solution for some implementations. For example, given a 2's-complement representation, evaluating -INT_MIN will probably give you -INT_MIN. But in fact, the behavior of evaluating that expression is undefined due to overflow, even if you assume 2's-complement. (Wraparound semantics are very common, but are not guaranteed.) Furthermore, the C standard does not require a 2's-complement representation; it also permits 1's-complement and sign-and-magnitude, neither of which has that extra negative value.

This program:

#include <stdio.h>
#include <limits.h>
int main(void) {
    int n = INT_MIN;
    printf("%d\n%d\n", n, -n); /* Warning: Undefined behavior for -n */
}

produces this output on my system:

-2147483648
-2147483648

Operations on C unsigned types have more strictly defined behavior. This program:

#include <stdio.h>
#include <limits.h>
int main(void) {
    unsigned int n = UINT_MAX / 2 + 1;
    printf("%u\n%u\n", n, -n);
}

gives this output on a system with 32-bit int (and no padding bits):

2147483648
2147483648

and will print two identical lines of output on any conforming implementation.

C++ has the same behavior (or undefined behavior) as C in this area.

In Perl, a large integer will fall over to a floating-point representation if it's too large to be represented as an integer -- but Perl scalars are complicated, and can simultaneously store more than one representation. On my 64-bit system, this Perl program:

#!/usr/bin/perl

use strict;
use warnings;

my $n = -2.0**63;
print $n, "\n", -$n, "\n";
printf "%d\n%d\n", $n, -$n;

gives this output:

-9.22337203685478e+18
9.22337203685478e+18
-9223372036854775808
-9223372036854775808

which I'm not entirely sure I can explain myself.

Python appears to fall back to some form of extended-precision integers, so the issue of overflow doesn't arise, and so there's no numeric value that is its own negation. A number of other languages (including, I think, most Lisp dialects) do the same thing.

In Ada, an integer overflow doesn't have undefined behavior; it's required to raise an exception. This program:

with Ada.Text_IO; use Ada.Text_IO;
procedure Foo is
    N: Integer := Integer'First;
begin
    Put_Line(Integer'Image(N));
    Put_Line(Integer'Image(-N));
end Foo;

produces just one line of output:

-2147483648

and then dies with a Constraint_Error exception.

And so on, and so on, and ....

So unless the instructor is just looking for zero as the answer, it depends very much on the context.

And looking at the question, why do you assume that 0 (which is a perfectly correct and obvious answer to the question as written, and apparently is the only correct answer in Java) isn't what the instructor was looking for?