查找非零整数 x,其中 x == -x?

2022-09-01 20:31:23

在我大学的一门关于算法和数据结构的课程中,我收到了这个问题:

哪个整数的位模式与他的负值相同?

表示:x == -x

我知道0有效,但我怀疑教练正在寻找其他数字x。它是什么x?你会怎么找到它?


答案 1

Integer.MIN_VALUE和Long.MIN_VALUE没有等效的正值,当您取这些值的负值时,您将获得相同的值。

负数与翻转所有位并添加一个位相同。即

-x = ~x + 1

所以 -0x80000000 = 0x7fffffff + 1 = 0x8000000

注意:Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE 这是负面的。此方法的 javadoc 中对此进行了概述。

从技术上讲,有许多答案和类型

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;

一个类似的Java益智游戏是;when 是以下表达式 。true

x != x + 0

编辑:浮点数同时具有 和 .这样的你可能会考虑一个不同的值,尽管它是这样的情况+0.0-0.0-0.00.0-0.0 == -(-0.0)

注意:注意:Double.compare(0.0, -0.0) > 0


答案 2

假设您采用有符号二进制补码格式的最低可表示数字。假设这个数字(称之为x)具有位模式,例如。要计算 -x,首先翻转所有位以获得 ,然后向其添加一个位。这会导致较大的纹波携带,再次产生该数字,即您开始时使用的数字。因此,您将拥有.对于 Java ints,此值为 -231100000...001111...11000....0x == -xInteger.MIN_VALUE

你实际上可以通过数学来解决这个问题。由于所有有符号二进制补码格式的数字都表示模数二的幂(例如,2d),则语句

x == -x

真正意味着

x == -x (mod 2d)

这意味着

2x == 0 (mod 2d)

因此,这个问题的解决方案是所有数字x的集合,其中2x是0 mod 2d。这些是任何整数 k 的 k × 2d 形式的数字。这些值中只有两个可以用 d + 1 位的有符号二进制补码格式表示,即 0 和 -2d。因此,最小可能的负数将始终等于其负值进行比较。

希望这有帮助!