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

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

При тестировании на проводнике компилятора 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

Кажется, я что-то упустил. Любые идеи?

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

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

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

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

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

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

-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представимо в типе результата, (a/b)*b + a%bравно a[...].

Включение оптимизации

Однако, используя unsignedтипы, оптимизация будет полностью правильной , удовлетворяя вышеуказанному соглашению:

unsigned(-1)%256 == 0xFF

Смотрите также это .

Другие языки

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

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

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

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

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

Эти sarзвуки команд мне , как «сдвиг арифметического права», заполняя освободившиеся биты со знаком битового значения.

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

% b = a - b * этаж (a / b)

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