Uma pergunta que recebi na minha última entrevista:
Projete uma função
f
, de modo que:f(f(n)) == -n
Onde
n
é um número inteiro assinado de 32 bits ; você não pode usar aritmética de números complexos.Se você não pode projetar essa função para todo o intervalo de números, projete-o para o maior intervalo possível.
Alguma ideia?
Respostas:
E se:
Em Python:
O Python promove automaticamente números inteiros com comprimentos arbitrários. Em outros idiomas, o maior número inteiro positivo excederá o limite, portanto funcionará para todos os números inteiros, exceto aquele.
Para fazê-lo funcionar com números reais, você precisa substituir n em (-1) n por
{ ceiling(n) if n>0; floor(n) if n<0 }
.Em C # (funciona para qualquer duplo, exceto em situações de estouro):
fonte
Você não disse que tipo de linguagem eles esperavam ... Aqui está uma solução estática (Haskell). É basicamente mexer com os 2 bits mais significativos:
É muito mais fácil em uma linguagem dinâmica (Python). Basta verificar se o argumento é um número X e retornar um lambda que retorne -X:
fonte
class C a b | a->b where { f :: a->b }
:;instance C Int (()->Int) where { f=const.negate }
;instance C (()->Int) Int where { f=($()) }
.Aqui está uma prova do porquê de tal função não existir, para todos os números, se ela não usar informações extras (exceto 32 bits de int):
Devemos ter f (0) = 0. (Prova: Suponha que f (0) = x. Então f (x) = f (f (0)) = -0 = 0. Agora, -x = f (f (x) )) = f (0) = x, o que significa que x = 0.)
Além disso, para qualquer
x
ey
, suponhaf(x) = y
. Nós queremosf(y) = -x
então. Ef(f(y)) = -y => f(-x) = -y
. Para resumir: sef(x) = y
, entãof(-x) = -y
, ef(y) = -x
, ef(-y) = x
.Portanto, precisamos dividir todos os números inteiros, exceto 0, em conjuntos de 4, mas temos um número ímpar desses números inteiros; além disso, se removermos o número inteiro que não possui uma contraparte positiva, ainda temos 2 números (mod4).
Se removermos os 2 números máximos restantes (pelo valor abs), podemos obter a função:
É claro que outra opção é não cumprir com 0 e obter os 2 números que removemos como bônus. (Mas isso é apenas um tolo se.)
fonte
n = -2147483648
(valor mínimo); você não podeabs(n)
, nesse caso, e o resultado será indefinido (ou uma exceção).Graças à sobrecarga em C ++:
fonte
Ou você pode abusar do pré-processador:
fonte
Isso é verdade para todos os números negativos.
Como há mais um número negativo do que números positivos para dois números inteiros de complemento,
f(n) = abs(n)
é válido para mais um caso que af(n) = n > 0 ? -n : n
solução que é a mesma quef(n) = -abs(n)
. Peguei você por um ...: DATUALIZAR
Não, não é válido para mais um caso, pois acabei de reconhecer pelo comentário do litb ...
abs(Int.Min)
apenas transbordará ...Também pensei em usar as informações do mod 2, mas concluí que elas não funcionam ... até cedo. Se bem feito, funcionará para todos os números, exceto
Int.Min
porque isso excederá.ATUALIZAR
Eu brinquei com ele por um tempo, procurando um bom truque de manipulação, mas não consegui encontrar um bom one-liner, enquanto a solução mod 2 se encaixa em um.
Em C #, isso se torna o seguinte:
Para fazê-lo funcionar para todos os valores, você tem que substituir
Math.Abs()
com(n > 0) ? +n : -n
e incluir o cálculo em umunchecked
bloco. Então você éInt.Min
mapeado para si mesmo como a negação desmarcada.ATUALIZAR
Inspirado por outra resposta, vou explicar como a função funciona e como construí-la.
Vamos começar do começo. A função
f
é aplicada repetidamente a um determinado valor,n
produzindo uma sequência de valores.A pergunta exige
f(f(n)) = -n
, ou seja, duas aplicações sucessivas def
negar o argumento. Duas outras aplicaçõesf
- quatro no total - negam que o argumento volte a render-sen
novamente.Agora há um ciclo óbvio de comprimento quatro. Substituindo
x = f(n)
e observando que a equação obtida sef(f(f(n))) = f(f(x)) = -x
mantém, produz o seguinte.Então, temos um ciclo de comprimento quatro com dois números e os dois números negados. Se você imaginar o ciclo como um retângulo, os valores negativos estão localizados em cantos opostos.
Uma das muitas soluções para construir esse ciclo é a seguinte, partindo de n.
Um exemplo concreto é esse ciclo
+1 => -2 => -1 => +2 => +1
. Estamos quase terminando. Observando que o ciclo construído contém um número positivo ímpar, seu sucessor par e ambos os números negam, podemos facilmente dividir os números inteiros em muitos desses ciclos (2^32
é um múltiplo de quatro) e descobrimos uma função que satisfaz as condições.Mas temos um problema com zero. O ciclo deve conter
0 => x => 0
porque o zero é negado para si mesmo. E porque o ciclo já indica0 => x
a seguir0 => x => 0 => x
. Este é apenas um ciclo de comprimento dois ex
é transformado em si mesmo após duas aplicações, não em-x
. Felizmente, há um caso que resolve o problema. SeX
igual a zero, obtemos um ciclo de comprimento um contendo apenas zero e resolvemos esse problema concluindo que o zero é um ponto fixo def
.Feito? Quase. Temos
2^32
números, zero é um ponto fixo que deixa2^32 - 1
números e devemos particionar esse número em ciclos de quatro números. Ruim que2^32 - 1
não é múltiplo de quatro - restarão três números que não estão em nenhum ciclo de comprimento quatro.Explicarei a parte restante da solução usando o conjunto menor de itegers assinados de 3 bits, que variam de
-4
até+3
. Terminamos com zero. Temos um ciclo completo+1 => -2 => -1 => +2 => +1
. Agora vamos construir o ciclo começando em+3
.O problema que surge é que
+4
não é representável como número inteiro de 3 bits. Nós+4
obteríamos negando-3
a+3
- o que ainda é um número inteiro válido de 3 bits - mas adicionando um a+3
(binário011
) produz100
binário. Interpretado como número inteiro não assinado,+4
mas temos que interpretá-lo como número inteiro assinado-4
. Portanto, na verdade,-4
para este exemplo ouInt.MinValue
para o caso geral, existe um segundo ponto fixo de negação aritmética inteira -0
eInt.MinValue
são mapeados para eles. Portanto, o ciclo é realmente o seguinte.É um ciclo de duração dois e, adicionalmente,
+3
entra no ciclo via-4
. Em conseqüência,-4
é corretamente mapeado para si mesmo após duas aplicações de funções,+3
é corretamente mapeado para-3
após duas aplicações de funções, mas-3
é erroneamente mapeado para si mesmo após duas aplicações de funções.Então construímos uma função que funciona para todos os números inteiros, exceto um. Podemos fazer melhor? Não nós não podemos. Por quê? Temos que construir ciclos de comprimento quatro e somos capazes de cobrir todo o intervalo inteiro até quatro valores. Os valores restantes são os dois pontos fixos
0
eInt.MinValue
devem ser mapeados para si mesmos e dois números inteiros arbitráriosx
e-x
que devem ser mapeados entre si por dois aplicativos de função.Para mapear
x
a-x
e vice-versa, devem formar um ciclo de quatro e que devem estar localizados em cantos opostos desse ciclo. Em conseqüência,0
eInt.MinValue
também deve estar em cantos opostos. Isto irá mapear corretamentex
e-x
mas trocar os dois pontos fixos0
eInt.MinValue
após duas aplicações de função e deixar-nos com duas entradas de falha. Portanto, não é possível construir uma função que funcione para todos os valores, mas temos uma que funcione para todos os valores, exceto um, e isso é o melhor que podemos alcançar.fonte
Usando números complexos, você pode efetivamente dividir a tarefa de negar um número em duas etapas:
O melhor é que você não precisa de nenhum código de manipulação especial. Apenas multiplicando por i faz o trabalho.
Mas você não tem permissão para usar números complexos. Então você precisa criar de alguma forma seu próprio eixo imaginário, usando parte do seu intervalo de dados. Como você precisa exatamente dos valores imaginários (intermediários) dos valores iniciais, você terá apenas metade do intervalo de dados.
Tentei visualizar isso na figura a seguir, assumindo dados de 8 bits assinados. Você teria que escalar isso para números inteiros de 32 bits. O intervalo permitido para n inicial é de -64 a +63. Aqui está o que a função faz para n positivo:
Para n negativo, a função usa o intervalo intermediário -65 ..- 128.
fonte
float
vsint
). O 'anel de 4 elementos' que muitas respostas descrevem requer 4 estados, que podem ser representados como 2 dimensões, cada uma com 2 estados. O problema com esta resposta é que ela requer espaço de processamento adicional (apenas 'funciona' para -64..63, mas precisa de espaço -128..127) e não indica explicitamente a fórmula escrita!Funciona, exceto int.MaxValue e int.MinValue
fonte
0
para0
e-2147483648
para,-2147483648
pois esses dois números são pontos fixos para o operador de negaçãox => -x
,. Para o restante dos números, siga as setas na imagem acima. Como fica claro na resposta de SurDin e seus comentários, haverá dois números, neste caso,2147483647
e-2147483647
sem nenhum outro par para trocar.A questão não diz nada sobre o que o tipo de entrada e valor de retorno da função
f
tem que ser (pelo menos não da maneira que você apresentou-o) ...... apenas quando n é um número inteiro de 32 bits,
f(f(n)) = -n
Então, que tal algo como
Se n for um número inteiro de 32 bits, a instrução
f(f(n)) == -n
será verdadeira.Obviamente, essa abordagem pode ser estendida para trabalhar com uma variedade ainda maior de números ...
fonte
para javascript (ou outras linguagens de tipo dinâmico), você pode fazer com que a função aceite um int ou um objeto e retorne o outro. ie
dando
Como alternativa, você pode usar a sobrecarga em uma linguagem fortemente tipada, embora isso possa violar as regras.
fonte
Dependendo da sua plataforma, alguns idiomas permitem manter o estado na função. VB.Net, por exemplo:
IIRC, C ++ também permitiu isso. Eu suspeito que eles estão procurando uma solução diferente.
Outra idéia é que, como eles não definiram o resultado da primeira chamada para a função, você pode usar ímpar / imparcialidade para controlar se deve inverter o sinal:
Adicione um à magnitude de todos os números pares e subtraia um da magnitude de todos os números ímpares. O resultado de duas chamadas tem a mesma magnitude, mas a única chamada em que é trocamos o sinal. Existem alguns casos em que isso não funciona (-1, max ou min int), mas funciona muito melhor do que qualquer outra coisa sugerida até o momento.
fonte
Explorando exceções de JavaScript.
fonte
Para todos os valores de 32 bits (com a ressalva de que -0 é -2147483648)
Você basicamente precisa emparelhar cada loop -x => x => -x com um loop ay => -y => y. Então eu emparelhei lados opostos do
split
.por exemplo, para números inteiros de 4 bits:
fonte
Uma versão C ++, provavelmente dobrando as regras um pouco, mas funciona para todos os tipos numéricos (flutuantes, ints, duplos) e até tipos de classe que sobrecarregam o menos unário:
fonte
x86 asm (estilo AT&T):
Código verificado, todos os possíveis números inteiros de 32 bits passados, erro com -2147483647 (underflow).
fonte
Usa globais ... mas e daí?
fonte
Essa solução Perl funciona para números inteiros, flutuantes e seqüências de caracteres .
Experimente alguns dados de teste.
Resultado:
fonte
n
foi uma corda que eu poderia fazer 548 torna-se "First_Time_548" e, em seguida, na próxima vez que ele é executado através da função ... if (prefixo == First_Time_ ") substituir 'First_Time_' com '-'Ninguém nunca disse que f (x) tinha que ser do mesmo tipo.
fonte
Na verdade, não estou tentando dar uma solução para o problema em si, mas tenho alguns comentários, pois a pergunta afirma que esse problema foi colocado como parte de uma entrevista (de trabalho?):
int.MinValue
paraint.MaxValue
e para cadan
chamada nesse intervalof(f(n))
e verificar se o resultado é-n
), dizendo que usaria o Desenvolvimento Orientado a Testes para obter essa função.Ah, essa resposta assume que a entrevista foi para uma posição relacionada à programação em C #. Obviamente, seria uma resposta tola se a entrevista fosse para uma posição relacionada à matemática. ;-)
fonte
Gostaria de mudar os 2 bits mais significativos.
Como você pode ver, é apenas uma adição, deixando de fora a parte transportada.
Como cheguei à resposta? Meu primeiro pensamento foi apenas uma necessidade de simetria. 4 voltas para voltar onde eu comecei. No começo eu pensei que era o código Gray de 2 bits. Então eu pensei que realmente o binário padrão é suficiente.
fonte
Aqui está uma solução inspirada no requisito ou afirma que números complexos não podem ser usados para resolver esse problema.
Multiplicar pela raiz quadrada de -1 é uma ideia que parece falhar apenas porque -1 não tem uma raiz quadrada sobre os números inteiros. Mas brincar com um programa como o mathematica fornece, por exemplo, a equação
e isso é quase tão bom quanto ter uma raiz quadrada de -1. O resultado da função precisa ser um número inteiro assinado. Portanto, vou usar uma operação de módulo modificado mods (x, n) que retorna o número inteiro y congruente para x módulo n mais próximo de 0. Apenas muito poucas linguagens de programação possuem uma operação de módulo, mas ela pode ser facilmente definida . Por exemplo, em python é:
Usando a equação acima, o problema agora pode ser resolvido como
Isso é satisfatório
f(f(x)) = -x
para todos os números inteiros no intervalo . Os resultados de também estão nessa faixa, mas é claro que a computação precisaria de números inteiros de 64 bits.[-2
31
-2, 2
31
-2]
f(x)
fonte
C # para um intervalo de 2 ^ 32 - 1 números, todos os números int32, exceto (Int32.MinValue)
impressões:
fonte
Essencialmente, a função precisa dividir o intervalo disponível em ciclos de tamanho 4, com -n no final oposto do ciclo de n. No entanto, 0 deve fazer parte de um ciclo de tamanho 1, porque caso contrário
0->x->0->x != -x
. Devido ao fato de 0 estar sozinho, deve haver 3 outros valores em nosso intervalo (cujo tamanho é um múltiplo de 4) que não estão em um ciclo adequado com 4 elementos.Eu escolhi estes valores estranhos extra para ser
MIN_INT
,MAX_INT
eMIN_INT+1
. Além disso,MIN_INT+1
irá mapearMAX_INT
corretamente, mas ficará preso lá e não mapeará de volta. Eu acho que esse é o melhor compromisso, porque ele tem a propriedade legal de apenas os valores extremos não funcionarem corretamente. Além disso, significa que funcionaria para todos os BigInts.fonte
Ninguém disse que tinha que ser apátrida.
Trapaça, mas não tanto quanto muitos exemplos. Ainda mais mal seria espiar a pilha para ver se o endereço do chamador é & f, mas isso será mais portátil (embora não seja seguro para threads ... a versão segura para threads usaria TLS). Ainda mais mal:
Obviamente, nenhuma dessas funciona muito bem para o caso de MIN_INT32, mas há muito pouco que você pode fazer sobre isso, a menos que tenha permissão para retornar um tipo mais amplo.
fonte
Eu poderia imaginar que usar o 31º bit como um bit imaginário ( i ) seria uma abordagem que suportaria metade da faixa total.
fonte
trabalha para n = [0 .. 2 ^ 31-1]
fonte
O problema declara "números inteiros assinados de 32 bits", mas não especifica se são dois ou dois complementos .
Se você usar um complemento-ones, todos os valores de 2 ^ 32 ocorrerão em ciclos de comprimento quatro - você não precisa de um caso especial para zero e também não precisa de condicionais.
Em C:
Isso funciona por
Após duas passagens, temos o inverso bit a bit do valor original. Que na representação de um complemento é equivalente a negação.
Exemplos:
fonte
: D
fonte
fonte
Eu gostaria de compartilhar meu ponto de vista sobre este problema interessante como matemático. Eu acho que tenho a solução mais eficiente.
Se bem me lembro, você nega um número inteiro de 32 bits assinado, apenas lançando o primeiro bit. Por exemplo, se n = 1001 1101 1110 1011 1110 0000 1110 1010, então -n = 0001 1101 1110 1011 1110 0000 1110 1010.
Então, como definimos uma função f que recebe um número inteiro de 32 bits assinado e retorna outro número inteiro de 32 bits assinado com a propriedade de que tomar f duas vezes é o mesmo que inverter o primeiro bit?
Deixe-me reformular a pergunta sem mencionar conceitos aritméticos como números inteiros.
Como definimos uma função f que pega uma sequência de zeros e uns de comprimento 32 e retorna uma sequência de zeros e uns do mesmo comprimento, com a propriedade de que tomar f duas vezes é o mesmo que inverter o primeiro bit?
Observação: se você puder responder à pergunta acima para casos de 32 bits, também poderá responder para casos de 64 bits, casos de 100 bits, etc. Basta aplicar f nos primeiros 32 bits.
Agora, se você puder responder à pergunta no caso de 2 bits, Voila!
E sim, acontece que alterar os 2 primeiros bits é suficiente.
Aqui está o pseudo-código
Observação: A etapa 2 e a etapa 3 juntas podem ser exibidas como (a, b) -> (-b, a). Parece familiar? Isso deve lembrá-lo da rotação de 90 graus do plano e da multiplicação pela raiz quadrada de -1.
Se eu apresentasse o pseudo-código sozinho, sem o longo prelúdio, pareceria um coelho, queria explicar como consegui a solução.
fonte