找到非零整数x,其中x == -x？

Question

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

哪个整数与其负值具有相同的位模式？

意思是:x == -x

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

Answer 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 Puzzler是; 何时是以下表达式true.

x != x + 0

编辑:浮点有+0.0和-0.0.这样你可能会考虑-0.0不同的值,0.0尽管情况就是如此-0.0 == -(-0.0)

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

Answer 2

假设您采用带符号二进制补码格式的最低可表示数字.比方说,这个数字(称之为x)有位模式100000...0.要计算-x,首先将所有位翻转到get 01111...1,然后再添加一个.这会导致较大的纹波进位,从而1000....0再次产生数字,这是您开始使用的数字.因此你会有x == -x.在Java int的情况下,该值为Integer.MIN_VALUE-2 ³¹.

你可以用数学方法解决这个问题.由于有符号二进制补码格式的所有数字都以两个幂(例如,2 ^d)的模数表示,因此该语句

x == -x

真正意思

x == -x(mod 2 ^d)

这意味着

2x == 0(mod 2 ^d)

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

希望这可以帮助!