LINUX.ORG.RU
Форум — Development  

Помогите распарсить код

 


0

2

Есть такой код сравнения двух чисел ( > ):

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

    //flatten back to range of 0 or 1.
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff &= 1;

    return diff;
}

Не могу распарсить как оно работает. Пробую на 4хбитных числах: 

int isGt(int a, int b)
{
#    a = 1100
#    b = 1110
    

    int diff = a ^ b;
    
# diff = 0010    
 
    diff |= diff >> 1;
    
# diff = 0010 | 1 = 0011    
    
    diff |= diff >> 2;
    
# diff = 0011 | 0 = 0011    
    
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

# diff = 0011

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
    
# diff = ~(110) | 1000 = 1001 & 0011 = 1
    
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

# diff = 1100 ^ 1000 = 0100
         1110 ^ 0111 = 1001
         0100 & 1001 = 0
            1 &    0 = 0 // <-- Сломалось, ибо должен быть 1


    //flatten back to range of 0 or 1.
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff &= 1;

    return diff;
}

Как оно работает?



Последнее исправление: CYB3R (всего исправлений: 1)
← C++ параллельный проход по нескольким контейнерам.
Смешанная компиляция. Как g++ подключает объектные файлы gcc? →

Как оно работает?

Конпелятор конпеляет из этого банарник, который содержит в себе инструкции для процессора, процессор выполняет его, ты видишь результат =)

Zhbert ★★★★★
()

очевидно, что алгоритм сравнения использует XOR

Harald ★★★★★
()
Ответ на: комментарий от mix_mix

Попендикулярно 

# diff = 0011

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
    
# diff = ~(1) | 1000 = 1110 & 0011 = 10
    
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

# diff = 1100 ^ 1000 = 0100
         1110 ^ 0111 = 1001
         0100 & 1001 = 0
           10 &    0 = 0 // <-- Сломалось, ибо должен быть 1

Edible
() автор топика

В чём проблема?

Ты заменил 0x80000000 на 0x8 и 0x7fffffff на 0x7. В таком случае a=1100_2=-3_10, b=1110_2=-1_10, т.е. a < b, isGt должна вернуть ноль.

anonymous
()
Ответ на: комментарий от anonymous

Один человек на весь ЛОР адекватный, да и тот анон. Спасибо.

Edible
() автор топика

ну давай разберём по частям, всё тобою написанное)))

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
// заполнили единичками всё от старшего различного бита до младшего 

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
// наибольший значащий бит

    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);
// для unsigned можно просто diff &= a, но тут нужно учесть минус.
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff &= 1;
// ну тут вроде всё понятно
    return diff;
}
f1u77y ★★★★
()
Ответ на: комментарий от anonymous

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

f1u77y ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← C++ параллельный проход по нескольким контейнерам.
Development
Смешанная компиляция. Как g++ подключает объектные файлы gcc? →