C код объяснение

Question

Существует следующая функция, которая, как предполагается сделать сравнение между 2 значения с плавающей точкой, но быстрее, чем обычные сравнения в некоторых конкретных случаях (например, на Cortex-A8)

int isGreater(float* f1, float* f2) 
{ 
    int i1, i2, t1, t2; 

    i1 = *(int*)f1; // reading float as integer 
    i2 = *(int*)f2; // reading float as integer 

    t1 = i1 >> 31; 
    i1 = (i1^t1) + (t1 & 0x80000001); 

    t2 = i2 >> 31; 
    i2 = (i2^t2) + (t2 & 0x80000001); 

    return i1 > i2; 
} 

Может кто-то объяснить как это точно работает?

Answer 1

Этот код использует структуру формата IEEE 754 для чисел с плавающей запятой. Сама структура была специально разработана для таких операций, чтобы быстро выполнять сравнительные операции.

Каждый одинарной точности стандарта IEEE 754 номер состоит из трех частей (в порядке от MSB до LSB):

• знаковый бит
• показатель часть (8 бит)
• мантиссы мантиссы (23 бита)

f1 больше f2 если:

• f1 положителен и f2 отрицательно
• f1 и f2 являются положительным, но f1 имеет больший показатель, чем f2
• f1 и f2 как положительный, так и иметь те же показатели, но f1 имеет большую мантиссу, чем f2
• в отличие от предыдущих двух, если f1 и f2 являются отрицательными

Можно просто сравнить числа с плавающей запятой как целые числа, если они были в представлении two's complement. К сожалению, IEEE 754 не использует два дополнения для представления отрицательных чисел, и поэтому этот код выполняет преобразование, чтобы иметь возможность просто сравнивать числа в виде целых чисел.

Вот шаг за шагом комментарии о том, что делает каждая строка кода:

i1 = *(int*)f1; // reading float as integer 
i2 = *(int*)f2; // reading float as integer 

Это один использует тот факт, что в большинстве 32-битных систем sizeof(int) == sizeof(float) читать числа с плавающей точкой в ​​регулярные подписал целочисленные переменные.

t1 = i1 >> 31; 

Этот фрагмент извлекает знаковый бит f1. Если f1 отрицательно, его MSB будет 1, и, следовательно, i1 будет отрицательным. Смещение его 31 бита вправо сохраняет знак и, следовательно, если i1 был отрицательным t1 имел бы все биты, установленные на 1 (равные -1). Если f1 был положительным, его знаковый бит будет 0, а в конце t1 будет равен 0.

i1 = (i1^t1) + (t1 & 0x80000001); 

Если знаковый бит был 1 эта линия будет выполнять преобразование в дополнение представления двоек, если f1 был отрицательным.

Вот как это работает: если f1 был положительным, то t1 является 0 и (i1^t1) бы просто i1 и (t1 & 0x80000001) будет 0 и в конце концов i1 бы просто сохранить свое первоначальное значение. Если f1 был отрицательным, то t1 будет иметь все биты, установленные на 1, и первое выражение на RHS будет битовой инверсией i1, а второе выражение будет равно 0x80000001. Таким образом, i1 будет преобразован в инверсию битов и будет добавлен 1. Но это приведет к положительному числу, так как MSB будет очищен, и поэтому добавляется 0x80000000, чтобы сохранить число отрицательным.

t2 = i2 >> 31; 
i2 = (i2^t2) + (t2 & 0x80000001); 

Выполните то же, что указано выше для f2.

return i1 > i2; 

Просто сравните два результате подписали целые числа. Большинство процессоров имеют специальные инструкции для выполнения подписанного сравнения в оборудовании.