Всегда ли в C верно, что ux - uy == - (y - x), когда x, y являются символами, и ux = (без знака) x, uy = (без знака) y? - PullRequest
Новая
       30

Всегда ли в C верно, что ux - uy == - (y - x), когда x, y являются символами, и ux = (без знака) x, uy = (без знака) y?

1 голос
/ 28 апреля 2020

У меня есть следующий код в C: 

char x, y; // Some random values
unsigned ux = (unsigned)x;
unsigned uy = (unsigned)y;

И мне нужно определить, является ли выражение ux - uy == -(y - x) всегда истинным или нет, и доказать это или привести контрпример.

Я не знаю, правда это или нет, потому что это разные типы целых чисел, с разными размерами, и два из них подписаны, а два других - без знака.

Ответы [ 2 ]

2 голосов
/ 28 апреля 2020

Вопрос более тонкий, чем кажется. Если это из интервью, вы можете подробно остановиться на char подписанности, которая определяется реализацией, размере этих типов, а также определенной реализации, целочисленном продвижении от char до int или unsigned int в зависимости от о размере и подписи типа char, о преобразованиях типов, подразумеваемых бинарными операторами, такими как ==, о разнице между вычитанием со знаком и без знака, о случайных значениях и неопределенном поведении, связанном с неопределенными переменными и арифметика со знаком c переполнение. Если вы освоите эти предметы, вы можете обнаружить, что интервьюер не может. Рекомендуется с особой осторожностью корректировать свою демонстрацию соответствующим образом.

  1. код в вопросе имеет неопределенное поведение по простой причине: 

    char x, y; // Some random values
unsigned ux = (unsigned)x;
unsigned uy = (unsigned)y;

    x и y не имеют случайных значений , они неинициализированы. Вычисления (unsigned)x, (unsigned)y и y - x все вызывают неопределенное поведение. Таким образом, как закодированное, равенство не имеет смысла, оно не определено.

  2. Предполагается, что вы инициализируете x и y до случайных значений , в общем В этом случае вопрос является ли выражение ux - uy == -(y - x) всегда верным или нет? Ответ NO , а вот контрпример:

    В архитектуре, где Тип char имеет тот же размер и подпись, что и int, выражение y - x может переполниться, например, если y = INT_MIN и x = 1, и это переполнение имеет неопределенное поведение. Следовательно, для этой архитектуры и этих значений выражение ux - uy == -(y - x) не является истинным, оно не определено.

  3. На более распространенных архитектурах, где char имеет 8 бит и, по крайней мере, int 16 бит, давайте изучим различные возможности:

    • in y - x, x и y повышены до int, так как этот тип может представлять все значения типа char независимо от того, подписан тип char или нет. y - x имеет тип int и находится в диапазоне [-255, 255] и -(y - x), также int находится в том же диапазоне. На этих архитектурах -(y - x) имеет то же значение, что и -y + x и x - y. Возникает вопрос: ux - uy == x - y?

    • Выражение ux - uy == x - y сравнивает выражение типа unsigned int с выражением типа int. Выражение int преобразуется в unsigned int, и сравнение выполняется для значений без знака.

    • Преобразование значения int со знаком в unsigned int выполняется путем добавления значения UINT_MAX + 1 к отрицательному значению и сохранению положительных значений. Результатом этой операции является вычисление арифметического c значения по модулю UINT_MAX+1.

    • Таким образом, выражение оценивается как:

      ((x мод (UINT_MAX + 1)) - (у мод (UINT_MAX + 1))) мод (UINT_MAX + 1) == (х - у) мод (UINT_MAX + 1)

    • оператор по модулю является дистрибутивным, а значения таковы, что x - y является арифметической c разницей x и y, независимо от подписи char.

    Следовательно, для архитектур, где sizeof(int) > 1 ответ - ДА , равенство выполняется для всех значений x и y.

0 голосов
/ 28 апреля 2020

Нет, есть много случаев, когда ux - uy == -(y - x) не соответствует действительности.

  • char имеет подпись, определяемую реализацией, поэтому нет портативного способа определить, содержат ли x и y положительные или отрицательные значения для начала.

  • x и y получат целое число, повышенное до int независимо от их подписи, потенциально расширенного знака.

  • Операнды == будут сбалансированы в соответствии с "обычным" арифметические c преобразования ", означая, что вы в конечном итоге неявно преобразуете правый операнд в тип без знака, независимо от того, какое значение оно имело изначально.

    Теоретически это делается способом, определяемым реализацией, но на практике он будет работать одинаково на всех системах дополнения реального мира 2.

Резюме: это код далек от хрупкости, чтобы работать надежно / переносимо из-за поведения, определенного реализацией, и неявного продвижения по службе. Возможно, имеется также некоторый недостаток / переполнение, которое может произойти при определенных входных данных.

Подробнее см. В этих сообщениях:
Является ли символ по умолчанию подписанным или неподписанным?
Неявные правила продвижения типов

Чтобы избежать подобных проблем, нужно быть осторожнее с выбранными типами. Избегайте арифметических чисел c для целочисленных типов. Обратите внимание на переменные диапазоны. Изучите различные правила продвижения неявных типов и как они могут вызвать проблемы с изменением подписи и т. Д. c.

...