Como posso calcular com segurança dois INTs não assinados no C ++?

StackOverflow https://stackoverflow.com/questions/3816446

  •  26-09-2019
  •  | 
  •  

Pergunta

Usando apenas matemática inteira, gostaria de "com segurança" em média duas INTs não assinadas no C ++.

O que quero dizer com "segurança" é evitar transbordamentos (e qualquer outra coisa que possa ser pensada).

Por exemplo, média 200 e 5000 é fácil:

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

Mas no caso de 4294967295 e 5000 então:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

O melhor que eu inventei é:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

Existem maneiras melhores?

Foi útil?

Solução

Sua última abordagem parece promissora. Você pode melhorar isso, considerando manualmente os bits mais baixos de A e B:

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

Isso fornece os resultados corretos caso A e B sejam estranhos.

Outras dicas

unsigned int average = low + ((high - low) / 2);

EDITAR

Aqui está um artigo relacionado: http://googlerearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Seu método não está correto se os dois números forem ímpares, por exemplo, 5 e 7, a média é 6, mas o seu método nº 3 retorna 5.

Experimente isso:

average = (a>>1) + (b>>1) + (a & b & 1)

Somente com operadores de matemática:

average = a/2 + b/2 + (a%2) * (b%2)

Se você não se importa com um pequeno conjunto em linha X86 (sintaxe GNU C), você pode aproveitar a sugestão do Supercat para usar Gire-com-carregamento Após um add para colocar os 32 bits altos do resultado completo de 33 bits em um registro.

Claro, você geralmente deve Mente usar em linha-asmo, porque derrota algumas otimizações (https://gcc.gnu.org/wiki/dontuseinlineasm). Mas aqui vamos nós de qualquer maneira:

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

o % modificador Para dizer ao compilador que os args são comutativos, na verdade, não ajuda a melhorar o ASM no caso que tentei, chamando a função com Y sendo um constante ou ponteiro-deref (operando da memória). Provavelmente, usando uma restrição correspondente para um operando de saída derrota isso, pois você não pode usá-lo com operando de leitura-gravação.

Como você pode ver no compilador de Godbolt Explorer, isso compila corretamente, e uma versão em que mudamos os operando para unsigned long, com o mesmo ASM embutido. Clang3.9 faz uma bagunça disso, e decide usar o "m" opção para o "rme" restrição, por isso armazena na memória e usa um operando de memória.

O RCR-BY-ONE não é muito lento, mas ainda são 3 UOPS em Skylake, com latência de 2 ciclo. É ótimo nas CPUs da AMD, onde o RCR tem latência de ciclo único. (Fonte: Tabelas de instrução de Agner Fog, veja também o tag wiki para links de desempenho x86). Ainda é melhor que a versão do @Sellibitze, mas pior que a versão dependente de ordem de @Sheldon. (Veja o código em Godbolt)

Mas lembre-se de que as otimizações em linha de base em linha como a propagação constante, portanto, qualquer versão Pure-C ++ será melhor nesse caso.

E a resposta correta é ...

(A&B)+((A^B)>>1)

O que você tem é bom, com os detalhes menores de que ele alegará que a média de 3 e 3 é 2. Acho que você não quer isso; Felizmente, há uma solução fácil:

unsigned int average = a/2 + b/2 + (a & b & 1);

Isso apenas aumenta a média de backup no caso de ambas as divisões foram truncadas.

Se o código for para um micro incorporado e se a velocidade for crítica, a linguagem de montagem poderá ser útil. Em muitos microcontroladores, o resultado do ADD naturalmente entraria no sinalizador de transporte, e existem instruções para transferi -lo de volta para um registro. Em um braço, a operação média (fonte e dest. Em registros) pode ser feita em duas instruções; Qualquer equivalente em língua C provavelmente produziria pelo menos 5, e provavelmente um pouco mais do que isso.

Aliás, em máquinas com tamanhos de palavras mais curtos, as diferenças podem ser ainda mais substanciais. Em uma série PIC-18 de 8 bits, a média de dois números de 32 bits levaria doze instruções. Fazer os turnos, add e correção levaria 5 instruções para cada turno, oito para o ADD e oito para a correção, então 26 (não é uma diferença de 2,5x, mas provavelmente mais significativa em termos absolutos).

(((a&b << 1) + (a^b)) >> 1) também é uma boa maneira.

Cortesia: http://www.ragestorm.net/blogs/?p=29

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

espera avg == 5.0 para este teste

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top