É ((a + (b & 255)) & 255) o mesmo que ((a + b) & 255)?

Eu estava navegando em algum código C ++ e encontrei algo assim:

(a + (b & 255)) & 255

O duplo E me incomodou, então pensei em:

(a + b) & 255

( ae bsão inteiros sem sinal de 32 bits)

Rapidamente escrevi um script de teste (JS) para confirmar minha teoria:

for (var i = 0; i < 100; i++) {
    var a = Math.ceil(Math.random() * 0xFFFF),
        b = Math.ceil(Math.random() * 0xFFFF);

    var expr1 = (a + (b & 255)) & 255,
        expr2 = (a + b) & 255;

    if (expr1 != expr2) {
        console.log("Numbers " + a + " and " + b + " mismatch!");
        break;
    }
}

Embora o script tenha confirmado minha hipótese (ambas as operações são iguais), ainda não confio nele, porque 1) aleatório e 2) não sou matemático, não tenho ideia do que estou fazendo .

Além disso, desculpe pelo título Lisp-y. Sinta-se à vontade para editá-lo.

Eles são os mesmos. Aqui está uma prova:

Primeiro observe a identidade (A + B) mod C = (A mod C + B mod C) mod C

Vamos reafirmar o problema considerando a & 255como substituto a % 256. Isso é verdade desdea não tem sinal.

assim (a + (b & 255)) & 255 é(a + (b % 256)) % 256

É o mesmo que (a % 256 + b % 256 % 256) % 256(apliquei a identidade declarada acima: observe que mode% são equivalentes para tipos não assinados).

Isso simplifica o (a % 256 + b % 256) % 256que se torna (a + b) % 256(reaplicar a identidade). Você pode então colocar o operador bit a bit de volta para dar

(a + b) & 255

completando a prova.

Na adição, subtração e multiplicação posicional de números sem sinal para produzir resultados sem sinal, os dígitos mais significativos da entrada não afetam os dígitos menos significativos do resultado. Isso se aplica tanto à aritmética binária quanto à aritmética decimal. Também se aplica à aritmética com sinais de "complemento de dois", mas não à aritmética com sinais de magnitude de sinal.

No entanto, temos que ter cuidado ao pegar regras da aritmética binária e aplicá-las a C (acredito que C ++ tem as mesmas regras que C nessas coisas, mas não tenho 100% de certeza) porque a aritmética C tem algumas regras misteriosas que podem nos enganar acima. A aritmética sem sinal em C segue regras de agrupamento binário simples, mas o estouro aritmético com sinal é um comportamento indefinido. Pior, em algumas circunstâncias, C irá "promover" automaticamente um tipo não assinado para int (assinado).

O comportamento indefinido em C pode ser especialmente insidioso. Um compilador burro (ou um compilador em um nível de otimização baixo) provavelmente fará o que você espera com base em seu conhecimento de aritmética binária, enquanto um compilador otimizador pode quebrar seu código de maneiras estranhas.

Portanto, voltando à fórmula da questão, a igualdade depende dos tipos de operando.

Se eles forem inteiros sem sinal cujo tamanho é maior ou igual ao tamanho de, intentão o comportamento de estouro do operador de adição é bem definido como um agrupamento binário simples. O fato de mascararmos ou não os 24 bits altos de um operando antes da operação de adição não tem impacto sobre os bits baixos do resultado.

Se eles forem inteiros não assinados cujo tamanho é menor que intentão eles serão promovidos a (assinados) int. O estouro de inteiros assinados é um comportamento indefinido, mas pelo menos em todas as plataformas que encontrei, a diferença de tamanho entre os diferentes tipos de inteiros é grande o suficiente para que uma única adição de dois valores promovidos não cause o estouro. Portanto, novamente podemos recorrer ao argumento aritmético simplesmente binário para considerar as declarações equivalentes.

Se eles forem inteiros assinados cujo tamanho é menor que int, então novamente o estouro não pode acontecer e em implementações de complemento de dois, podemos confiar no argumento aritmético binário padrão para dizer que eles são equivalentes. Em implementações de magnitude de sinal ou complemento de uns, eles não seriam equivalentes.

OTOH se ae bfossem inteiros assinados cujo tamanho era maior ou igual ao tamanho de int, então, mesmo em implementações de complemento de dois, há casos em que uma instrução seria bem definida enquanto a outra seria um comportamento indefinido.

Lema: a & 255 == a % 256para não assinado a.

Sem sinal apode ser reescrita como m * 0x100 + balguns unsigned m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Resulta de ambas as definições quea & 255 == b == a % 256 .

Além disso, precisamos de:

• a propriedade distributiva: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• a definição de adição sem sinal, matematicamente: (a + b) ==> (a + b) % (2 ^ 32)

Portanto:

(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255      // def'n of addition
                      = ((a + (b % 256)) % (2^32)) % 256      // lemma
                      = (a + (b % 256)) % 256                 // because 256 divides (2^32)
                      = ((a % 256) + (b % 256 % 256)) % 256   // Distributive
                      = ((a % 256) + (b % 256)) % 256         // a mod n mod n = a mod n
                      = (a + b) % 256                         // Distributive again
                      = (a + b) & 255                         // lemma

Então sim, é verdade. Para inteiros sem sinal de 32 bits.

E quanto a outros tipos inteiros?

• Para inteiros sem sinal de 64 bits, todos os itens acima se aplica tão bem, apenas substituindo 2^64a 2^32.
• Para inteiros não assinados de 8 e 16 bits, a adição envolve a promoção para int. Isso intdefinitivamente não transbordará nem será negativo em nenhuma dessas operações, portanto, todas permanecem válidas.
• Para inteiros assinados , se for a+bou a+(b&255)estouro, é um comportamento indefinido. Portanto, a igualdade não pode ser mantida - há casos em que o (a+b)&255comportamento é indefinido, mas (a+(b&255))&255não é.

Sim, (a + b) & 255está bem.

Lembra da adição na escola? Você adiciona números dígito a dígito e adiciona um valor de transporte à próxima coluna de dígitos. Não há como uma coluna posterior (mais significativa) de dígitos influenciar uma coluna já processada. Por causa disso, não faz diferença se você zerar os dígitos apenas no resultado ou também primeiro em um argumento.

O que foi dito acima nem sempre é verdade, o padrão C ++ permite uma implementação que quebraria isso.

Tal Deathstation 9000 : - ) teria que usar 33 bits int, se o OP significasse unsigned short"inteiros sem sinal de 32 bits". Se isso unsigned intfosse feito, o DS9K teria que usar um bit de 32 bits inte um de 32 bits unsigned intcom um bit de preenchimento. (Os inteiros não assinados devem ter o mesmo tamanho que suas contrapartes assinadas de acordo com §3.9.1 / 3, e bits de preenchimento são permitidos em §3.9.1 / 1.) Outras combinações de tamanhos e bits de preenchimento também funcionam.

Pelo que eu posso dizer, esta é a única maneira de quebrá-lo, porque:

• A representação inteira deve usar um esquema de codificação "puramente binário" (§3.9.1 / 7 e a nota de rodapé), todos os bits, exceto os bits de preenchimento e o bit de sinal, devem contribuir com um valor de 2 ⁿ
• promoção int é permitida apenas se intpode representar todos os valores do tipo de origem (§4.5 / 1), portanto, intdeve ter pelo menos 32 bits contribuindo para o valor, mais um bit de sinal.
• O intnão pode ter mais bits de valor (sem contar o bit de sinal) do que 32, caso contrário, uma adição não pode estourar.

Você já tem a resposta inteligente: aritmética sem sinal é aritmética de módulo e, portanto, os resultados serão válidos, você pode provar isso matematicamente ...

Uma coisa legal sobre computadores, porém, é que eles são rápidos. Na verdade, eles são tão rápidos que enumerar todas as combinações válidas de 32 bits é possível em um período de tempo razoável (não tente com 64 bits).

Então, no seu caso, eu pessoalmente gosto de apenas jogá-lo em um computador; levo menos tempo para me convencer de que o programa está correto do que para me convencer de que a prova matemática está correta e que não supervisionei um detalhe na especificação ¹ :

#include <iostream>
#include <limits>

int main() {
    std::uint64_t const MAX = std::uint64_t(1) << 32;
    for (std::uint64_t i = 0; i < MAX; ++i) {
        for (std::uint64_t j = 0; j < MAX; ++j) {
            std::uint32_t const a = static_cast<std::uint32_t>(i);
            std::uint32_t const b = static_cast<std::uint32_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Isso enumera todos os valores possíveis de ae bno espaço de 32 bits e verifica se a igualdade é mantida ou não. Caso contrário, ele imprime o gabinete que não funcionou, que você pode usar como uma verificação de integridade.

E, de acordo com Clang : a igualdade é mantida .

Além disso, dado que as regras aritméticas são agnósticas quanto à largura de bits (acima int da largura de bit), essa igualdade se manterá para qualquer tipo de inteiro sem sinal de 32 bits ou mais, incluindo 64 bits e 128 bits.

Nota: Como um compilador pode enumerar todos os padrões de 64 bits em um período de tempo razoável? Eu não posso. Os loops foram otimizados. Caso contrário, todos nós teríamos morrido antes do término da execução.

Inicialmente, provei isso apenas para inteiros sem sinal de 16 bits; infelizmente C ++ é uma linguagem insana para a qual pequenos inteiros (larguras de bits menores que int) são convertidos primeiro int.

#include <iostream>

int main() {
    unsigned const MAX = 65536;
    for (unsigned i = 0; i < MAX; ++i) {
        for (unsigned j = 0; j < MAX; ++j) {
            std::uint16_t const a = static_cast<std::uint16_t>(i);
            std::uint16_t const b = static_cast<std::uint16_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: "
                      << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

E mais uma vez, de acordo com Clang : a igualdade é válida .

Bem, aí está :)

¹ É claro que, se um programa acionar inadvertidamente o comportamento indefinido, isso não provaria muito.

A resposta rápida é: ambas as expressões são equivalentes

• uma vez que ae bsão inteiros sem sinal de 32 bits, o resultado é o mesmo, mesmo em caso de estouro. A aritmética sem sinal garante isso: um resultado que não pode ser representado pelo tipo inteiro sem sinal resultante é o módulo reduzido do número que é um maior que o maior valor que pode ser representado pelo tipo resultante.

A resposta longa é: não existem plataformas conhecidas onde essas expressões sejam diferentes, mas a Norma não garante isso, por causa das regras de promoção integral.

• Se o tipo de ae b(inteiros de 32 bits sem sinal) tiver uma classificação superior int, o cálculo será executado como sem sinal, módulo 2 ³² , e produzirá o mesmo resultado definido para ambas as expressões para todos os valores de ae b.

• Por outro lado, se o tipo de ae bfor menor que int, ambos são promovidos para inte o cálculo é realizado usando aritmética assinada, em que o estouro invoca um comportamento indefinido.

  • Se inttiver pelo menos 33 bits de valor, nenhuma das expressões acima pode estourar, então o resultado está perfeitamente definido e tem o mesmo valor para ambas as expressões.

  • Se inttiver exatamente 32 bits de valor, o cálculo pode estourar para ambas as expressões, por exemplo, valores a=0xFFFFFFFFe b=1causaria um estouro em ambas as expressões. Para evitar isso, você precisa escrever ((a & 255) + (b & 255)) & 255.

• A boa notícia é que essas plataformas não existem ¹ .

¹ Mais precisamente, essa plataforma real não existe, mas pode-se configurar um DS9K para exibir esse comportamento e ainda estar em conformidade com o C Standard.

Idêntico assumindo nenhum estouro . Nenhuma das versões é realmente imune a transbordamento, mas a versão dupla e mais resistente a ele. Não conheço um sistema em que um estouro, neste caso, seja um problema, mas posso ver o autor fazendo isso, caso haja um.

Sim, você pode provar isso com aritmética, mas há uma resposta mais intuitiva.

Ao adicionar, cada bit influencia apenas aqueles mais significativos do que ele mesmo; nunca aqueles menos significativos.

Portanto, o que quer que você faça com os bits mais altos antes da adição não mudará o resultado, desde que você mantenha apenas os bits menos significativos do que o bit mais baixo modificado.

A prova é trivial e deixada como um exercício para o leitor

Mas, para realmente legitimar isso como uma resposta, sua primeira linha de código diz pegue os últimos 8 bits de b** (todos os bits mais altos do bconjunto para zero) e adicione isso aa e, em seguida, pegue apenas os últimos 8 bits do resultado configurando todos os mais altos bits para zero.

A segunda linha diz adicionar aeb e tirar os últimos 8 bits com todos os bits mais altos zero.

Apenas os últimos 8 bits são significativos no resultado. Portanto, apenas os últimos 8 bits são significativos na (s) entrada (s).

** últimos 8 bits = 8 LSB

Também é interessante notar que a saída seria equivalente a

char a = something;
char b = something;
return (unsigned int)(a + b);

Como acima, apenas os 8 LSB são significativos, mas o resultado é um unsigned intcom todos os outros bits zero. O a + birá transbordar, produzindo o resultado esperado.