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

92

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.

Martin
fonte
4
Que idioma é esse script? Retorna Math.random()um número inteiro ou duplo em [0,1)? Não acho que seu roteiro (melhor que eu saiba) reflete o problema que você colocou.
Brick
7
O que é código c / c ++? Eles são idiomas diferentes.
Weather Vane
14
Você não pode reproduzir o comportamento que está tentando testar em JS. É por isso que todo mundo é só você quanto à escolha do idioma. JS não é fortemente tipado e a resposta depende criticamente do tipo das variáveis ​​em C / C ++. O JS é um absurdo completo, dada a pergunta que você fez.
Brick
4
@WeatherVane Isso é essencialmente pseudo-código, usando os nomes de função Javascript. Sua pergunta é sobre o comportamento de &e +em números inteiros sem sinal em C e C ++.
Barmar de
11
Lembre-se de que "Escrevi um programa de teste e obtive a resposta que esperava para todas as entradas possíveis" não é realmente uma garantia de que algo se comportará como você espera. O comportamento indefinido pode ser desagradável assim; apenas dando resultados inesperados depois de se convencer de que seu código está certo.

Respostas:

78

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.

Bate-Seba
fonte
81
É uma prova matemática, ignorando a possibilidade de estouro. Considere A=0xFFFFFFFF, B=1, C=3. A primeira identidade não é válida. (Overflow não vai ser um problema para aritmética sem sinal, mas é uma coisa um pouco diferente.)
AlexD
4
Na verdade, (a + (b & 255)) & 255é o mesmo que (a + (b % 256)) % N % 256, onde Né maior que o valor máximo sem sinal. (a última fórmula deve ser interpretada como aritmética de inteiros matemáticos)
17
Provas matemáticas como essa não são apropriadas para provar o comportamento de inteiros em arquiteturas de computador.
Jack Aidley
25
@JackAidley: Eles são apropriados quando feitos corretamente (o que não é, devido à negligência em considerar o estouro).
3
@Shaz: Isso é verdade para o script de teste, mas não faz parte da pergunta feita.
21

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.

plugwash
fonte
20

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 é.
Barry
fonte
17

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 n
  • 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.
Alain
fonte
2
Existem muitas outras operações além da adição, onde o lixo nos bits altos não afeta o resultado nos bits baixos em que você está interessado. Veja esta P&R sobre o complemento de 2 , que usa x86 asm como caso de uso, mas também se aplica a inteiros binários sem sinal em qualquer situação.
Peter Cordes
2
Embora seja um direito de todos votar anonimamente, sempre aprecio um comentário como uma oportunidade de aprender.
alain
2
Esta é de longe a resposta / argumento mais fácil de entender, IMO. O transporte / empréstimo em adição / subtração se propaga apenas dos bits baixos para os bits altos (da direita para a esquerda) em binário, o mesmo que em decimal. IDK por que alguém iria negar isso.
Peter Cordes
1
@Bathsheba: CHAR_BIT não precisa ser 8. Mas os tipos não assinados em C e C ++ precisam se comportar como inteiros binários base2 normais de alguma largura de bit. Acho que isso requer que UINT_MAX seja 2^N-1. (N pode nem ser necessário para ser um múltiplo de CHAR_BIT, eu esqueci, mas tenho certeza que o padrão requer que o wraparound aconteça módulo algum poder de 2.) Eu acho que a única maneira de você obter estranheza é promovendo a um tipo assinado que é largo o suficiente para segurar aou, bmas não largo o suficiente para segurar a+bem todos os casos.
Peter Cordes
2
@Bathsheba: sim, felizmente C-as-portable-assembly-language realmente funciona principalmente para tipos não assinados. Nem mesmo uma implementação C propositalmente hostil pode quebrar isso. São apenas tipos assinados onde as coisas são horríveis para bit-hacks verdadeiramente portáteis em C, e um Deathstation 9000 pode realmente quebrar seu código.
Peter Cordes
14

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 1 :

#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á :)


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

Matthieu M.
fonte
1
você diz que é fácil fazer com valores de 32 bits, mas na verdade usa 16 bits ...: D
Willi Mentzel
1
@WilliMentzel: Essa é uma observação interessante. Inicialmente queria dizer que se funciona com 16 bits então funcionará da mesma forma com 32 bits, 64 bits e 128 bits porque o Padrão não tem comportamento específico para larguras de bits diferentes ... porém lembrei que na verdade funciona para larguras de bits menores do que int: pequenos inteiros são primeiro convertidos para int(uma regra estranha). Então, na verdade, tenho que fazer a demonstração com 32 bits (e depois se estende para 64 bits, 128 bits, ...).
Matthieu M.
2
Visto que você não pode avaliar todos (4294967296 - 1) * (4294967296 - 1) resultados possíveis, você reduz de alguma forma? Na minha opinião, MAX deveria ser (4294967296 - 1) se você for assim, mas nunca terminará em nossa vida como você disse ... então, afinal não podemos mostrar a igualdade em um experimento, pelo menos não em um como você descrever.
Willi Mentzel
1
Testar isso na implementação do complemento de one 2 não prova que é portátil para magnitude de sinal ou complemento de um com larguras do tipo Deathstation 9000. por exemplo, um tipo estreito sem sinal pode promover a 17 bits, intque pode representar todas as possibilidades uint16_t, mas onde a+bpode estourar. Isso é apenas um problema para tipos não assinados mais estreitos do que int; C requer que os unsignedtipos sejam inteiros binários, então o wraparound acontece módulo uma potência de 2
Peter Cordes
1
Concordou que C é muito portátil para seu próprio bem. Seria muito bom se eles padronizassem o complemento de 2, deslocamentos aritméticos para a direita para sinalizado e uma maneira de fazer aritmética assinada com semântica de quebra em vez de semântica de comportamento indefinido, para aqueles casos em que você deseja quebra de linha. Então C poderia mais uma vez ser útil como um montador portátil, em vez de um campo minado graças aos compiladores de otimização modernos que tornam inseguro deixar qualquer comportamento indefinido (pelo menos para sua plataforma de destino. O comportamento indefinido apenas em implementações de Deathstation 9000 está ok, como você apontar).
Peter Cordes
4

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 32 , 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 1 .


1 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.

chqrlie
fonte
3
Seu segundo subfaixa requer (1) aé menor que int(2) inttem 32 bits de valor (3) a=0xFFFFFFFF. Isso não pode ser verdade.
Barry
1
@Barry: O único caso que parece atender aos requisitos é o de 33 bits int, onde há 32 bits de valor e um bit de sinal.
Ben Voigt
2

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.

Loren Pechtel
fonte
1
O OP especificado: (aeb são inteiros sem sinal de 32 bits) . A menos que inttenha 33 bits de largura, 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.
chqrlie
2

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.

Francesco Dondi
fonte
0

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.

user3728501
fonte
Não, não seria. A matemática de char acontece como int e char pode ser assinado.
Antti Haapala