Почему (INT) ((неподписанные INT) ((целое) v)?

Question

The website in which I found this code

int v, sign; 
// or, to avoid branching on CPUs with flag registers (IA32): 
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else 0. 

Этот оператор присваивает переменной знак со знаком переменной V (или -1 или 0). Интересно, почему (int)((unsigned int)((int)v) используется вместо простого против?

Answer 1

Цитируя C Стандарт 6.5.7p5:

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

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

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

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

sign = -(v > 0); 

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

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

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

Выражение может быть упрощено:

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

Обратите внимание, что если право сдвига определяется как тиражирование биты для вашей платформы (почти универсальное поведение с текущими процессорами), то выражение будет гораздо проще (предполагается, что 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 

Answer 2

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

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

Answer 3

Обратите внимание, что вы извлекли фрагмент выражения в свой вопрос (вы указываете (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, если v является отрицательным и 0, если это v ноль или положительный - вот что говорит комментарий.