Почему (int) ((unsigned int) ((int) v)?

Ответ 1

Цитирование стандарта C 6.5.7p5:

Результат E1 → E2 - это правые позиции E2 в E1. Если E1 имеет неподписанный тип, или если E1 имеет подписанный тип и неотрицательное значение, значение результата является неотъемлемой частью частного E1/2E2. Если E1 имеет подписанный тип и отрицательное значение, результирующее значение определяется реализацией.

Автор пишет, как реализовать функцию sign(int v), которая возвращает -1 для отрицательных чисел и 0 для 0 и положительных чисел эффективно. Наивный подход заключается в следующем:

int sign(int v) {
    if (v < 0)
        return -1;
    else
        return 0;
}

Но это решение может скомпилировать код, который выполняет сравнение и ветвь на флажках CPU, установленных при сравнении. Это неэффективно. Он предлагает более простое и более прямое решение:

sign = -(v > 0);

Но это вычисление по-прежнему требует сравнения и ветвления на процессорах, которые не дают результаты сравнения непосредственно в виде логических значений. Процессоры с флаговыми регистрами обычно устанавливают различные флаги в инструкциях сравнения или даже в большинстве арифметических команд. Поэтому он предлагает другое решение, основанное на смещении знакового бита, но, как указано в Стандарте, он не может полагаться на результат правого смещения отрицательного значения.

Листинг v как unsigned устраняет эту проблему, потому что правильно заданы значения без сдвига справа. Предполагая, что бит знака находится в наивысшем положении, что справедливо для всех современных процессоров, но не соответствует стандарту C, правое смещение (unsigned)v на меньшее, чем количество бит в его типе, дает значение 1 для отрицательные значения и 0 в противном случае. Отрицание результата должно приводить к ожидаемым значениям -1 для отрицательных v и 0 для положительных и нулевых v. Но выражение без знака, поэтому обычное отрицание будет производить UINT_MAX или 0, что, в свою очередь, вызывает арифметическое переполнение при сохранении в int или даже просто в качестве (int). Возвращая этот результат обратно к int, прежде чем отрицать его, правильно вычисляет желаемый результат, -1 для отрицательных v и 0 для положительного или нулевого v.

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

Выражение можно упростить как:

sign = -(int)((unsigned)v >> (sizeof(int) * CHAR_BIT - 1));

Обратите внимание, что если правое смещение определяется как репликация бит для вашей платформы (почти универсальное поведение с текущими CPU), выражение будет намного проще (предполагая int v):

sign = v >> (sizeof(v) * CHAR_BIT - 1));   // works on x86 CPUs

Страница bithacks https://graphics.stanford.edu/~seander/bithacks.html, очень поучительная, содержит подробное объяснение:

int v;      // we want to find the sign of v
int sign;   // the result goes here 

// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0);  // if v < 0 then -1, else 0. 
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1); 

Последнее выражение выше оценивает знак = v → 31 для 32-битных целых чисел. Это одна операция быстрее, чем очевидный путь, sign = - (v < 0). Этот трюк работает, потому что, когда целые числа со сдвигом сдвинуты вправо, значение крайнего левого бита копируется в другие биты. Крайний левый бит равен 1, когда значение отрицательное и 0 в противном случае; все 1 бит дает -1. К сожалению, это поведение специфично для архитектуры.

В качестве эпилога я бы рекомендовал использовать наиболее читаемую версию и полагаться на компилятор для создания наиболее эффективного кода:

sign = -(v < 0);

Как можно проверить на этой странице, озаглавленной: http://gcc.godbolt.org/# компиляция вышеуказанного кода с помощью gcc -O3 -std=c99 -m64 действительно выводит код ниже для всех решений выше, даже самый наивный оператор if/else:

sign(int):
    movl    %edi, %eax
    sarl    $31, %eax
    ret

Ответ 2

Обратите внимание, что вы извлекли фрагмент выражения в свой вопрос (вы указываете (int)((unsigned int)((int)v), у которого есть еще одна левая скобка (, чем правые скобки )). Выражение RHS оператора присваивания полностью:

-(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

Если вы добавили несколько пробелов, вы найдете:

-(int) (  (unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)  );
       ^  ^            ^^      ^    ^                          ^  ^
       |  +------------++------+    +--------------------------+  |
       +----------------------------------------------------------+

То есть внешний прилив (int) применяется ко всем:

((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

Внутреннее литье в (int) литье пусто; его результат сразу бросается на unsigned int. Литье (unsigned int) гарантирует, что правильный сдвиг будет хорошо определен. Выражение в целом определяет, является ли самый старший бит 0 или 1. Внешний int преобразует результат обратно в int, а - затем отрицает его, поэтому выражение -1 if v отрицательный, а 0, если v равен нулю или положителен - это то, что говорит комментарий.

Ответ 3

Сначала он переходит в int, затем в unsigned int, затем выполняет сдвиг, затем возвращается к int и, наконец, отрицает результат и сохраняет его в sign. Беззнаковое кастинг - это тот, который может повлиять на результат, поскольку он заставит логический сдвиг (который будет заполнен нулем), в отличие от арифметического сдвига (который будет подписать расширение).

Обратите внимание, что они действительно хотят арифметического сдвига, но я не верю, что C гарантирует его доступность, что, по-видимому, является причиной того, что они вручную выполняют отрицание логически сдвинутого знакового бита.