Uma das perguntas mais complicadas feitas em uma entrevista.
Troque os valores de duas variáveis como a=10
e b=15
.
Geralmente, para trocar dois valores de variáveis, precisamos da terceira variável como:
temp=a;
a=b;
b=temp;
Agora, o requisito é trocar os valores de duas variáveis sem usar a terceira variável.
Respostas:
Usando o algoritmo de troca xor
Por que o teste?
O teste é para garantir que xey tenham localizações de memória diferentes (em vez de valores diferentes). Isso ocorre porque,
(p xor p) = 0
e se xey compartilham o mesmo local de memória, quando um é definido como 0, ambos são definidos como 0. Quando * x e * y são 0, todas as outras operações xor em * x e * y serão iguais 0 (porque são iguais), o que significa que a função definirá * x e * y como 0.Se eles tiverem os mesmos valores, mas não o mesmo local de memória, tudo funcionará conforme o esperado
Isso deve ser usado?
Em casos gerais, não. O compilador otimizará a variável temporária e, dado que a troca é um procedimento comum, ele deve produzir o código de máquina ideal para sua plataforma.
Veja, por exemplo, este programa de teste rápido escrito em C.
Compilado usando:
A versão xor leva
Onde a versão com a variável temporária leva:
fonte
a forma geral é:
no entanto, você deve potencialmente estar atento a estouros e também nem todas as operações têm um inverso bem definido para todos os valores em que a operação está definida. por exemplo, * e / trabalhar até que A ou B seja 0
xor é particularmente agradável, pois é definido para todos os ints e é seu próprio inverso
fonte
fonte
a+b
transbordar?int
,unsigned short
...), ele ainda funciona no final, mesmo com excesso, porque se a + b transborda, em seguida, a - b será estouro negativo. Com esses tipos de inteiros básicos, os valores simplesmente rolam.unsigned
tipos inteiros está OK e sempre funciona. Em tipos assinados, ele invocaria um comportamento indefinido no estouro.Ninguém sugeriu usar
std::swap
, ainda.Eu não uso nenhuma variável temporária e dependendo do tipo de
a
eb
da implementação pode haver uma especalização que também não. A implementação deve ser escrita sabendo se um 'truque' é apropriado ou não. Não adianta tentar adivinhar.De forma mais geral, provavelmente gostaria de fazer algo assim, pois funcionaria para tipos de classe, permitindo que o ADL encontrasse uma sobrecarga melhor, se possível.
Claro, a reação do entrevistador a essa resposta pode dizer muito sobre a vaga.
fonte
std::
, definido pelo usuárioswap
implementações pelo usuário para tipos definidos pelo usuário também estão disponíveis para chamada (isso é o que significa "funcionaria para tipos de classe, permitindo que o ADL encontre uma sobrecarga melhor, se possível").std::swap
usa memória temporária adicional em sua implementação não? cplusplus.com/reference/utility/swapComo já notado por manu, o algoritmo XOR é um algoritmo popular que funciona para todos os valores inteiros (isso inclui ponteiros então, com alguma sorte e fundição). Para ser mais completo, gostaria de mencionar outro algoritmo menos poderoso com adição / subtração:
Aqui, você deve ter cuidado com overflows / underflows, mas, caso contrário, funciona perfeitamente. Você pode até tentar isso em floats / doubles no caso de XOR não ser permitido neles.
fonte
std::swap()
? Claro, você pode converter ponteiros em inteiros e vice-versa (assumindo que haja um tipo inteiro grande o suficiente, o que não é garantido), mas não foi isso que você sugeriu; você sugeriu que os ponteiros são inteiros, não que eles podem ser convertidos em inteiros. Sim, a resposta aceita não funcionará para indicadores. A resposta de Charles Bailey usandostd::swap
é realmente a única correta.std::swap
pode ser implementado sem usar uma terceira variável.Perguntas estúpidas merecem respostas adequadas:
O único bom uso da
register
palavra - chave.fonte
Trocar dois números usando a terceira variável seja assim,
Trocar dois números sem usar a terceira variável
fonte
fonte
cout << "Enter the two no=:"
esperar para lercout << "Now enter the two no in reverse order:"
a+b
oua-b
estoura Além disso,void main()
é inválido e<conio.h>
não é padrão.Já que a solução original é:
Você pode torná-lo um revestimento duplo usando:
Em seguida, transforme-o em um forro usando:
fonte
y
é lido e escrito na mesma expressão sem ponto de sequência intermediário.Se você mudar um pouco a pergunta para perguntar sobre 2 registros de montagem em vez de variáveis, você pode usar também a
xchg
operação como uma opção e a operação de pilha como outra.fonte
xchg
operação você está se referindo? A questão não especifica uma arquitetura de CPU.Considere
a=10
,b=15
:fonte
a=10
eb=1.5
.Atualização: neste, estamos pegando a entrada de dois inteiros do usuário. Então, estamos usando o XOR bit a bit para trocá-los.
Digamos que temos dois inteiros
a=4
eb=9
em seguida:fonte
Aqui está mais uma solução, mas um único risco.
código:
qualquer valor no local a + 1 será substituído.
fonte
*(&a+1)
pode muito bem serb
.void main()
é inválido.<conio.h>
não é padrão (e você nem mesmo o usa).Claro, a resposta C ++ deve ser
std::swap
.No entanto, também não há uma terceira variável na seguinte implementação de
swap
:Ou, como uma linha:
fonte
fonte
esse é o algoritmo de troca XOR correto
você deve garantir que os locais de memória sejam diferentes e também que os valores reais sejam diferentes porque A XOR A = 0
fonte
Você pode fazer .... de maneira fácil ... dentro de uma linha Lógica
ou
fonte
b
é lido e modificado na mesma expressão, sem ponto de sequência intermediário.fonte
A melhor resposta seria usar o XOR e usá-lo em uma linha seria legal.
x, y são variáveis e a vírgula entre elas introduz os pontos de sequência para que não se tornem dependentes do compilador. Felicidades!
fonte
Vamos ver um exemplo simples de c para trocar dois números sem usar a terceira variável.
programa 1:
Resultado:
Antes da troca a = 10 b = 20 Após a troca a = 20 b = 10
Programa 2: Usando * e /
Vamos ver outro exemplo para trocar dois números usando * e /.
Resultado:
Antes da troca a = 10 b = 20 Após a troca a = 20 b = 10
Programa 3: Fazendo uso do operador XOR bit a bit:
O operador XOR bit a bit pode ser usado para trocar duas variáveis. O XOR de dois números x e y retorna um número que tem todos os bits como 1 sempre que os bits de x e y diferem. Por exemplo, XOR de 10 (In Binary 1010) e 5 (In Binary 0101) é 1111 e XOR de 7 (0111) e 5 (0101) é (0010).
Resultado:
Após a troca: x = 5, y = 10
Programa 4:
Ninguém sugeriu usar std :: swap, ainda.
Eu não uso nenhuma variável temporária e dependendo do tipo de aeb, a implementação pode ter uma especialização que também não. A implementação deve ser escrita sabendo se um 'truque' é apropriado ou não.
Problemas com os métodos acima:
1) A abordagem baseada na multiplicação e divisão não funciona se um dos números for 0, já que o produto se torna 0 independentemente do outro número.
2) Ambas as soluções aritméticas podem causar estouro aritmético. Se x e y forem muito grandes, a adição e a multiplicação podem sair do intervalo inteiro.
3) Quando usamos ponteiros para uma variável e fazemos uma troca de função, todos os métodos acima falham quando ambos os ponteiros apontam para a mesma variável. Vamos dar uma olhada no que acontecerá neste caso se ambos estiverem apontando para a mesma variável.
// Método baseado em XOR bit a bit
// Método baseado em aritmética
Vamos ver o seguinte programa.
Resultado :
Após a troca (& x, & x): x = 0
A troca de uma variável com ela mesma pode ser necessária em muitos algoritmos padrão. Por exemplo, veja esta implementação do QuickSort onde podemos trocar uma variável com ele mesmo. O problema acima pode ser evitado colocando uma condição antes da troca.
Produto :
Após a troca (& x, & x): x = 10
fonte
Talvez fora do assunto, mas se você sabe o que está trocando uma única variável entre dois valores diferentes, pode ser capaz de fazer lógica de array. Cada vez que essa linha de código é executada, ela troca o valor entre 1 e 2.
fonte
Você poderia fazer:
Ou use make_tuple ao trocar mais de duas variáveis:
Mas não tenho certeza se internamente std :: tie usa uma variável temporária ou não!
fonte
Em javascript:
Esteja ciente do tempo de execução de ambas as opções.
Ao executar este código, eu o medi.
Como você pode ver (e como muitos disseram), a troca no lugar (xor) leva muito tempo do que a outra opção que usa a variável temp.
fonte
R está faltando uma atribuição concorrente, conforme proposto por Edsger W. Dijkstra em A Discipline of Programming , 1976, ch.4, p.29. Isso permitiria uma solução elegante:
fonte
É muito simples, mas pode gerar um alerta.
fonte
b=a
é realizado antes ou depoisa + b
.solução de linha única para trocar dois valores na linguagem c.
fonte
fonte