Por que (a% 256) é diferente de (a & 0xFF)?

Sempre presumi que, ao fazer (a % 256)o otimizador, usaria naturalmente uma operação bit a bit eficiente, como se eu escrevesse (a & 0xFF).

Ao testar no compilador 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

E ao tentar o outro código:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Parece que estou perdendo completamente alguma coisa. Alguma ideia?

Não é o mesmo. Tente num = -79e você obterá resultados diferentes das duas operações. (-79) % 256 = -79, enquanto (-79) & 0xffé algum número positivo.

Usando unsigned int, as operações são as mesmas e o código provavelmente será o mesmo.

PS- Alguém comentou

Eles não devem ser os mesmos, a % bé definido como a - b * floor (a / b).

Não é assim que é definido em C, C ++, Objective-C (ou seja, todos os idiomas em que o código da pergunta seria compilado).

Resposta curta

-1 % 256produz -1e não o 255que é -1 & 0xFF. Portanto, a otimização estaria incorreta.

Resposta longa

C ++ tem a convenção de que (a/b)*b + a%b == a, o que parece bastante natural. a/bsempre retorna o resultado aritmético sem a parte fracionária (truncando para 0). Como conseqüência, a%btem o mesmo sinal que aou é 0.

A divisão -1/256cede 0e, portanto, -1%256deve estar -1em conformidade com a condição acima ( (-1%256)*256 + -1%256 == -1). Isto é obviamente diferente do -1&0xFFque é 0xFF. Portanto, o compilador não pode otimizar da maneira que desejar.

A seção relevante no padrão C ++ [expr.mul §4] a partir do N4606 declara:

Para operandos integrais, o /operador produz o quociente algébrico com qualquer parte fracionária descartada; se o quociente a/bé representável no tipo de resultado, (a/b)*b + a%bé igual a a[...].

Ativando a otimização

No entanto, usando unsignedtipos, a otimização estaria completamente correta , atendendo à convenção acima:

unsigned(-1)%256 == 0xFF

Veja também isso .

Outras línguas

Isso é tratado de maneira muito diferente em diferentes linguagens de programação, como você pode consultar na Wikipedia .

Desde C ++ 11, num % 256deve ser não positivo se numfor negativo.

Portanto, o padrão de bits dependeria da implementação de tipos assinados no seu sistema: para um primeiro argumento negativo, o resultado não é a extração dos 8 bits menos significativos.

Seria diferente se numno seu caso fosse unsigned: hoje em dia eu quase esperaria que um compilador fizesse a otimização que você cita.

Não tenho uma visão telepática do raciocínio do compilador, mas, no caso de, %há a necessidade de lidar com valores negativos (e as rodadas de divisão em direção a zero), enquanto &o resultado é sempre os 8 bits mais baixos.

A sarinstrução soa para mim como "shift aritmetic right", preenchendo os bits desocupados com o valor do bit de sinal.

Matematicamente falando, o módulo é definido como o seguinte:

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

Isso aqui deve esclarecer para você. Podemos eliminar o piso para números inteiros porque a divisão inteira é equivalente ao piso (a / b). No entanto, se o compilador usar um truque geral, como você sugere, ele precisará funcionar para todos os a e todos os b. Infelizmente, isso simplesmente não é o caso. Matematicamente falando, seu truque é 100% correto para números inteiros não assinados (vejo uma resposta declarar números inteiros quebrados, mas posso confirmar ou negar isso como -a% b deve ser positivo). No entanto, você pode fazer esse truque para todos os b? Provavelmente não. É por isso que o compilador não faz isso. Afinal, se o módulo fosse facilmente escrito como uma operação bit a bit, adicionaríamos um circuito de módulo como para adição e outras operações.