Почему (a % 256) отличается от (A & 0xFF)?

Question

Почему (a % 256) отличается от (A & 0xFF)?

Я всегда предполагал, что при выполнении (a % 256) оптимизатор, естественно, будет использовать эффективную побитовую операцию, как если бы я написал (a & 0xFF).

при тестировании на компиляторе explorer gcc-6.2 (- O3):

// Type your code here, or load an example.

int mod(int num) {

    return num % 256;

}



mod(int):

    mov     edx, edi

    sar     edx, 31

    shr     edx, 24

    lea     eax, [rdi+rdx]

    movzx   eax, al

    sub     eax, edx

    ret

и при попытке другого кода:

// Type your code here, or load an example.

int mod(int num) {

    return num & 0xFF;

}



mod(int):

    movzx   eax, dil

    ret

кажется, что я полностью упускаю что-то.
Есть идеи?

464 5

c++optimization

5 ответов:

Comments

Ничего не найдено.

gnasher729 · Accepted Answer · 2016-11-10 22:03:40

это не то же самое. Попробуй num = -79, и вы получите разные результаты от обеих операций. (-79) % 256 = -79, в то время как (-79) & 0xff некоторое положительное число.

используя unsigned int, операции одинаковы, и код, вероятно, будет таким же.

PS - кто-то прокомментировал

они не должны быть одинаковыми, a % b определяется как a - b * floor (a / b).

это не так, как это определено в C, C++, Objective-C (т. е. все языки, где код в вопросе будет компилироваться).

Ralph Tandetzky · Accepted Answer · 2016-11-22 10:12:32

короткий ответ:

-1 % 256 доходность -1, а не 255 что это -1 & 0xFF. Поэтому оптимизация будет некорректной.

ответ

C++ имеет соглашение, что (a/b)*b + a%b == a, которое кажется вполне естественным. a/b всегда возвращает арифметический результат без дробной части (усечение до 0). Как следствие, a%b имеет тот же знак,a или равно 0.

отдела -1/256 доходность 0 и отсюда -1%256 должно быть -1 для выполнения вышеуказанного условия ((-1%256)*256 + -1%256 == -1). Это явно отличается от -1&0xFF что это 0xFF. Следовательно, компилятор не может оптимизировать так, как вы хотите.

соответствующий раздел стандарт C++ [expr.mul §4] по состоянию на N4606 гласит:

для целочисленных операндов / оператор дает алгебраическое частное с любой отброшенной дробной частью; если частное a/b is представимый в виде результата,(a/b)*b + a%b равна a [...].

включение оптимизации
, используя unsigned типы, оптимизация будет полностью правильной, удовлетворяя вышеуказанной Конвенции:
unsigned(-1)%256 == 0xFF
см. также этой.

другие языки

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

Bathsheba · Accepted Answer · 2016-11-08 18:47:36

Начиная С C++11, num % 256 должен быть неположительным, если num отрицательный.

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

другое дело, если num в вашем случае был unsigned: в эти дни я почти ожидал компилятор, чтобы сделать оптимизацию, которую вы цитируете.

Cheers and hth. - Alf · Accepted Answer · 2016-11-08 11:33:16

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

The sar инструкция звучит для меня как "сдвиг арифметики вправо", заполняя освобожденные биты значением бита знака.

The Great Duck · Accepted Answer · 2016-11-10 03:55:03

математически говоря, модуль определяется следующим образом:

a % b = a-b * floor (a/b)

Это прямо здесь должно прояснить это для вас. Мы можем исключить пол для целых чисел, потому что целочисленное деление эквивалентно полу(a/b). Однако, если бы компилятор использовал общий трюк, как вы предлагаете, он должен был бы работать для всех a и всех b. к сожалению, это просто не так. Математически говоря, ваш трюк на 100% верны для целых чисел без знака (Я вижу, что ответ состоял из целых чисел со знаком, но я не могу подтвердить или опровергнуть это, поскольку-A % b должен быть положительным). Однако, можете ли вы сделать этот трюк для всех b? Скорее всего, нет. Вот почему компилятор этого не делает. В конце концов, если бы модуль был легко записан как одна побитовая операция, то мы бы просто добавили схему по модулю, как для сложения и других операций.