c++ - resto - Qual é a melhor opção para dividir um número inteiro por 2?
resto da divisão em c float (16)
Qual é a melhor opção e por que dividir o número inteiro por 2?
Depende do que você entende por melhor .
Se você quer que seus colegas te odeiem ou que seu código seja difícil de ler, eu definitivamente escolheria a primeira opção.
Se você quiser dividir um número por 2, vá com o segundo.
Os dois não são equivalentes, eles não se comportam da mesma forma se o número for negativo ou dentro de expressões maiores - o desvio de bits tem precedência menor que + ou - , a divisão tem precedência mais alta.
Você deve escrever seu código para expressar qual é a sua intenção. Se o desempenho é sua preocupação, não se preocupe, o otimizador faz um bom trabalho com esse tipo de micro-otimização.
Qual das seguintes técnicas é a melhor opção para dividir um inteiro por 2 e por quê?
Aqui x é um inteiro.
A resposta para isso dependerá do ambiente em que você está trabalhando.
Se você está trabalhando em um microcontrolador de 8 bits ou qualquer coisa sem suporte de hardware para multiplicação, espera-se que a mudança de bits seja comum e, embora o compilador quase certamente gire x /= 2 em x >>= 1 , a presença de uma divisão O símbolo levantará mais sobrancelhas naquele ambiente do que usando uma mudança para efetuar uma divisão.
Se você estiver trabalhando em um ambiente de desempenho crítico ou seção de código, ou se seu código puder ser compilado com a otimização de compilador desativada, x >>= 1 com um comentário explicando seu raciocínio provavelmente será melhor apenas para fins de clareza de propósito.
Se você não estiver em uma das condições acima, torne seu código mais legível simplesmente usando x /= 2 . É melhor salvar o próximo programador que, por acaso, olha para o seu código com o dobro de 10 segundos em sua operação de turno do que provar desnecessariamente que você sabia que a mudança era mais eficiente sem a otimização do compilador.
Todos estes assumem números inteiros sem sinal. A simples mudança provavelmente não é o que você deseja para assinar. Além disso, DanielH traz um bom ponto sobre o uso de x *= 0.5 para determinadas linguagens como o ActionScript.
Basta usar dividir ( / ), presumindo que seja mais claro. O compilador otimizará de acordo.
Dê uma olhada na saída do compilador para ajudá-lo a decidir. Eu executei este teste no x86-64 com
Veja também as saídas do compilador online no godbolt .
O que você vê é que o compilador usa uma instrução sarl (mudança aritmética à direita) em ambos os casos, portanto reconhece a similaridade entre as duas expressões. Se você usar a divisão, o compilador também precisará ajustar para números negativos. Para fazer isso, ele desloca o bit de sinal para o bit de menor ordem e adiciona isso ao resultado. Isso corrige o problema off-by-one ao mudar os números negativos, comparado ao que uma divisão faria.
Como o caso de divisão faz dois turnos, enquanto o caso de turno explícito apenas faz um, agora podemos explicar algumas das diferenças de desempenho medidas por outras respostas aqui.
Código C com saída de montagem:
Para dividir, sua entrada seria
int div2signed(int a) {
e isso compila para
da mesma forma para a mudança
Enquanto x >> 1 é mais rápido que x / 2, o uso adequado de >> ao lidar com valores negativos é um pouco mais complicado. Requer algo semelhante ao seguinte:
public static int ShiftDivBy2(this int x) {
return (x < 0 ? x + 1 : x) >> 1;
Estou dizendo para o propósito de programar competições. Geralmente eles têm entradas muito grandes onde a divisão por 2 ocorre muitas vezes e é conhecido que a entrada é positiva ou negativa.
x >> 1 será melhor que x / 2. Eu verifiquei no ideone.com, executando um programa onde mais de 10 ^ 10 divisão por 2 operações ocorreram. x / 2 levou quase 5.5s, enquanto x >> 1 levou quase 2.6s para o mesmo programa.
Eu diria que há várias coisas a serem consideradas.
O bitshift deve ser mais rápido, já que nenhum cálculo especial é realmente necessário para mudar os bits, no entanto, como apontado, há possíveis problemas com números negativos. Se você é assegurado para ter números positivos, e está procurando a velocidade então eu recomendaria bitshift.
O operador de divisão é muito fácil para os humanos lerem. Então, se você está procurando por legibilidade de código, você poderia usar isso. Observe que o campo de otimização do compilador já percorreu um longo caminho, portanto, tornar o código fácil de ler e entender é uma boa prática.
Dependendo do hardware subjacente, as operações podem ter velocidades diferentes. A lei de Amdal é tornar o caso comum rápido. Então você pode ter hardware que pode executar operações diferentes mais rápido do que outras. Por exemplo, multiplicar por 0,5 pode ser mais rápido do que dividir por 2. (Concedido, você pode precisar usar o piso da multiplicação se quiser impor a divisão de números inteiros).
Se você está atrás do desempenho puro, eu recomendo criar alguns testes que poderiam fazer as operações milhões de vezes. Teste a execução várias vezes (seu tamanho de amostra) para determinar qual delas é estatisticamente melhor com seu sistema operacional / hardware / compilador / código.
Knuth disse:
Otimização prematura é a raiz de todo o mal.
Então eu sugiro usar x /= 2;
Desta forma o código é fácil de entender e também acho que a otimização desta operação nessa forma, não significa uma grande diferença para o processador.
O primeiro parece dividir-se? Não. Se você quiser dividir, use x / 2 . O compilador pode otimizá-lo para usar o bit-shift, se possível (é chamado de redução de força), o que torna uma micro-otimização inútil se você fizer isso sozinho.
Obviamente, se você está escrevendo seu código para o próximo cara que o lê, escolha a clareza de "x / 2".
No entanto, se a velocidade for o seu objetivo, tente as duas formas e o tempo nos resultados. Alguns meses atrás eu trabalhei em uma rotina de convolução bitmap que envolvia passar por uma matriz de inteiros e dividir cada elemento por 2. Eu fiz todos os tipos de coisas para otimizá-lo, incluindo o antigo truque de substituir "x >> 1" por "x / 2 ".
Quando eu realmente cronometrei os dois caminhos, descobri, para minha surpresa, que x / 2 era mais rápido que x >> 1
Isso estava usando o Microsoft VS2008 C ++ com as otimizações padrão ativadas.
Torne suas intenções mais claras ... por exemplo, se você quiser dividir, use x / 2 e deixe o compilador otimizá-lo para mudar o operador (ou qualquer outra coisa).
Os processadores de hoje não permitem que essas otimizações tenham impacto no desempenho de seus programas.
Use x = x / 2; OR x /= 2; Porque é possível que um novo programador trabalhe nele no futuro. Por isso, será mais fácil para ele descobrir o que está acontecendo na linha de código. Todos podem não estar cientes de tais otimizações.
X / Y é um correto ... e ">>" operador de deslocamento .. se quisermos dividir um número inteiro, podemos usar o operador (/) de dividendos. operador de deslocamento é usado para mudar os bits ..
x = x / 2; x / = 2; podemos usar assim ..
geralmente o turno da direita divide:
q = i >> n; is the same as: q = i / 2**n;
Isso às vezes é usado para acelerar programas com o custo de clareza. Eu não acho que você deveria fazer isso. O compilador é inteligente o suficiente para executar o aumento de velocidade automaticamente. Isso significa que colocar uma mudança não lhe dá nada à custa da clareza .
Dê uma olhada nesta página do Practical C ++ Programming.
x = x / 2; é o código adequado para usar .. mas uma operação depende do seu próprio programa de como a saída que você queria produzir.
x / 2 é mais claro, e x >> 1 não é muito mais rápido (de acordo com um micro-benchmark, cerca de 30% mais rápido para uma Java JVM). Como outros notaram, para números negativos, o arredondamento é ligeiramente diferente, então você deve considerar isso quando quiser processar números negativos. Alguns compiladores podem converter automaticamente x / 2 para x >> 1 se souberem que o número não pode ser negativo (mesmo que eu não consiga verificar isso).
Mesmo x / 2 pode não usar a instrução de CPU de divisão (lenta), porque alguns atalhos são possíveis , mas ainda são mais lentos que x >> 1 .
(Esta é uma questão C / C ++, outras linguagens de programação possuem mais operadores. Para Java também existe o deslocamento à direita sem sinal, x >>> 1 , que é novamente diferente. Ele permite calcular corretamente o valor médio (médio) de dois valores, de modo que (a + b) >>> 1 retornará o valor médio mesmo para valores muito grandes de a e b Isso é necessário, por exemplo, para pesquisa binária se os índices da matriz puderem ficar muito grandes. muitas versões da pesquisa binária , porque eles usaram (a + b) / 2 para calcular a média. Isso não funciona corretamente. A solução correta é usar (a + b) >>> 1 vez disso.)
simbolo resto quociente linguagem inteira float divisão divisao dev c++ c optimization division micro-optimization