Поиск ненулевого целого x, где x == -x?
В курсе по алгоритмам и структурам данных в моем университете я получил этот вопрос:
Какое целое число имеет тот же бит-шаблон, что и его отрицательное значение?
Средство: x == -x
Я знаю, что 0 работает, но я подозреваю, что инструктор искал какое-то другое число x. Что это такое? Как бы вы его нашли?
Ответы
Ответ 1
Integer.MIN_VALUE и Long.MIN_VALUE не имеют эквивалентного положительного значения, и когда вы принимаете отрицательное значение, вы получаете одинаковое значение.
Отрицательный - это то же самое, что сбросить все биты и добавить один. то есть.
-x = ~x + 1
So -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
EDIT: плавающая точка имеет как +0.0
, так и -0.0
. A такое, что вы можете рассмотреть -0.0
другое значение 0.0
, хотя это так: -0.0 == -(-0.0)
Примечание: Double.compare(0.0, -0.0) > 0
Примечание:
Ответ 2
Предположим, что вы берете наименьшее возможное представимое число в подписанном формате с двумя дополнениями. Скажем, это число (назовите его x) имеет битовый шаблон 100000...0
, например. Чтобы вычислить -x, вы сначала переверните все биты, чтобы получить 01111...1
, а затем добавьте его в него. Это приводит к большому пульсации, что приводит к числу 1000....0
, которое является номером, с которого вы начали. Таким образом, у вас будет x == -x
. В случае Java ints это значение Integer.MIN_VALUE
, которое равно -2 31.
Вы можете на самом деле вычислить это математически. Так как все числа в подписанном формате с двумя дополнениями представлены по модулю некоторой мощности двух (скажем, 2 d), то утверждение
x == -x
Действительно означает
x == -x (mod 2 d)
Это означает, что
2x == 0 (mod 2 d)
Следовательно, решения этой задачи являются множеством всех чисел x, где 2x равно 0 mod 2 d. Это числа вида k & times; 2 d для любого целого k. Только два из этих значений могут быть представлены в подписанном формате с двумя дополнениями с d + 1 битами, а именно 0 и -2 d. Поэтому минимально возможное отрицательное число всегда будет сравниваться с его отрицательным значением.
Надеюсь, это поможет!
Ответ 3
Для 8-битного целого числа: 1000 0000
подписано это -128, а unsigned - 128
Ответ 4
Посмотрите на это по-другому: все подписанные примитивные целочисленные типы представляют целые числа в диапазоне
-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. Поэтому, чтобы получить его в диапазоне, нам нужно добавить 2 N * k для некоторого 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 включительно. Но все остальное применяется одинаково.
Ответ 5
Вопрос, как сказано, неоднозначен.
0
- это, конечно, очевидное решение, и, как уже обсуждали другие, в Java нет других решений (так как помечен вопрос).
В C для любого знакового целочисленного типа минимальное значение данного типа может быть решением для некоторых реализаций. Например, учитывая представление 2's-комплемента, оценка -INT_MIN
, вероятно, даст вам -INT_MIN
. Но на самом деле поведение оценки этого выражения undefined из-за переполнения, даже если вы принимаете 2'-дополнение. (Семантика Wraparound очень распространена, но не гарантируется.) Кроме того, стандарт C не требует представления 2's-complement; он также допускает 1'-дополнение и знак и величину, ни одна из которых не имеет этого дополнительного отрицательного значения.
Эта программа:
#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
и напечатает две идентичные строки вывода при любой соответствующей реализации.
С++ имеет такое же поведение (или поведение undefined) как 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 переполнение целых чисел не имеет поведения undefined; это потребовало возбуждения исключения. Эта программа:
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), не является тем, что искал инструктор для?