24

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

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

表示：x == -x

我知道 0 有效，但我怀疑讲师正在寻找其他数字 x。x是什么？你会怎么找到它？

4

5 回答 5

32

Integer.MIN_VALUE 和 Long.MIN_VALUE 没有等效的正值，当你取它们的负值时，你会得到相同的值。

负数与翻转所有位并加一相同。IE

-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 注意：

于 2013-10-24T20:57:32.520 回答
10

假设您采用带符号二进制补码格式的最小可能表示数字。例如，假设这个数字（称为 x）具有位模式100000...0。要计算 -x，您首先翻转所有位以获得01111...1，然后将其加一。这会导致较大的波纹进位，从而1000....0再次产生数字，这是您开始使用的数字。这样你就有了x == -x。对于 Java 整数，该值为Integer.MIN_VALUE，即 -2 31。

你实际上可以用数学方法计算出来。由于带符号二进制补码格式的所有数字都表示为模 2 的某个幂（例如 2 d），因此该语句

x == -x

真正意思

x == -x (mod 2 d )

这意味着

2x == 0 (mod 2 d )

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

希望这可以帮助！

于 2013-10-24T20:57:28.213 回答
1

对于 8 位整数：1000 0000有符号的为 -128，无符号的为 128

于 2013-10-24T20:57:56.053 回答
0

换个角度看：所有带符号的原始整数类型都表示范围内的整数

-2 N-1至 2 N-1 -1

（含），其中 N 是位数。每当执行任何数学整数运算时，如果数学结果是某个超出该范围的数字 Z（“溢出”），则实际结果将是 R = Z + 2 N * k，其中 k 是某个正整数或负整数选择这样 R 将在 -2 N-1到 2 N-1 - 1 的范围内。所以说 x = -2 N-1，我们计算 -x。数学结果是 Z = 2 N-1，但这超出了范围，因为 Z > 2 N-1 -1。所以为了让它在范围内，我们需要为一些 k 添加 2 N * k，并且 k 必须是 -1。因此实际结果是 R = 2 N-1 + (2 N )*(-1) = 2 N-1- 2 N = -2 N-1，这是 x 的原始值。所以这是一个使 x == -x 的值。

Java 只有带符号的整数类型，但在具有无符号类型的语言中，无符号类型的范围是 0 到 2 N -1，包括 0 到 2 N -1。但其他一切都以同样的方式适用。

于 2013-10-24T21:10:26.663 回答
0

如前所述，这个问题是模棱两可的。

0当然是显而易见的解决方案，正如其他人所讨论的那样，Java 中没有其他解决方案（这就是问题的标记方式）。

在 C 中，对于任何有符号整数类型，给定类型的最小值可能是某些实现的解决方案。例如，给定一个 2 的补码表示，评估可能-INT_MIN会给你. 但事实上，由于溢出，评估该表达式的行为是未定义的，即使您假设 2 的补码。（环绕语义很常见，但不能保证。）此外，C 标准不需要 2 的补码表示；它还允许 1's-complement 和 sign-and-magnitude，它们都没有额外的负值。-INT_MIN

这个程序：

#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 */
}

在我的系统上产生这个输出：

-2147483648
-2147483648

C 无符号类型的操作具有更严格定义的行为。这个程序：

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

在具有 32 位int（且无填充位）的系统上给出此输出：

2147483648
2147483648

并将在任何符合要求的实现上打印两条相同的输出行。

C++ 在这方面与 C 具有相同的行为（或未定义的行为）。

在 Perl 中，如果一个大整数太大而无法表示为整数，那么它会落入浮点表示形式——但是 Perl 标量很复杂，并且可以同时存储多个表示形式。在我的 64 位系统上，这个 Perl 程序：

#!/usr/bin/perl

use strict;
use warnings;

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

给出这个输出：

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

我不完全确定我可以解释自己。

Python 似乎回退到某种形式的扩展精度整数，因此不会出现溢出问题，因此没有数值是它自己的否定。许多其他语言（包括，我认为，大多数 Lisp 方言）做同样的事情。

在 Ada 中，整数溢出没有未定义的行为；它需要引发异常。这个程序：

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;

只产生一行输出：

-2147483648

然后Constraint_Error异常死亡。

等等，等等，还有....

因此，除非讲师只是在寻找零作为答案，否则它在很大程度上取决于上下文。

看看这个问题，你为什么认为0（这是对所写问题的完全正确和明显的答案，显然是 Java 中唯一正确的答案）不是教师想要的？

于 2013-10-25T01:45:54.560 回答