Fonction de conception f (f (n)) == -n

841

Une question que j'ai posée lors de ma dernière interview:

Concevez une fonction f, telle que:

f(f(n)) == -n

nest un entier signé 32 bits ; vous ne pouvez pas utiliser l'arithmétique des nombres complexes.

Si vous ne pouvez pas concevoir une telle fonction pour toute la gamme de nombres, concevez-la pour la plus large gamme possible.

Des idées?

Gumbo
la source
2
Pour quel travail était cette interview?
tymtam

Réponses:

377

Que diriez-vous:

f (n) = signe (n) - (-1) n * n

En Python:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python promeut automatiquement les entiers en longueurs arbitraires. Dans d'autres langues, le plus grand entier positif débordera, donc cela fonctionnera pour tous les entiers sauf celui-ci.


Pour le faire fonctionner pour des nombres réels, vous devez remplacer le n dans (-1) n par { ceiling(n) if n>0; floor(n) if n<0 }.

En C # (fonctionne pour tout double, sauf en cas de débordement):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}
RossFabricant
la source
10
Brisé pour -1, car -1 * 0 est toujours 0
Joel Coehoorn
3
Non ça ne l'est pas. f (-1) = 0. f (0) = 1
1800 INFORMATION
5
Il est cependant cassé pour 1. f (1) = 0. f (0) = 1
1800 INFORMATION
18
Hmm, sauver l'état avec des nombres pairs et impairs, j'aurais dû y penser.
Inconnu le
38
Je pense que la chose la plus importante n'est pas la fonction réelle (il existe une infinité de solutions), mais le processus par lequel vous pouvez construire une telle fonction.
pyon
440

Vous n'avez pas dit à quel type de langage ils s'attendaient ... Voici une solution statique (Haskell). Il s'agit essentiellement de jouer avec les 2 bits les plus significatifs:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

C'est beaucoup plus facile dans un langage dynamique (Python). Vérifiez simplement si l'argument est un nombre X et renvoyez un lambda qui renvoie -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()
viraptor
la source
23
Cool, j'adore ça ... la même approche en JavaScript: var f = function (n) {return (typeof n == 'function')? n (): fonction () {return -n; }}
Mark Renouf
C'est probablement juste que mon Haskell est très rouillé, mais avez-vous vérifié cela pour (f 0)? Il semble que cela devrait produire le même résultat que (f 0x80000000), au moins si nous avons affaire à des entiers 32 bits avec une arithmétique enveloppante (sur l'opération de négation). Et ce serait mauvais.
Darius Bacon,
11
L'intervieweur moyen ne sait même ce qu'est une construction lambda est ?
Jeremy Powell
4
Bien sûr, une telle astuce de type tricherie fonctionne aussi dans Haskell, même si elle est statique: class C a b | a->b where { f :: a->b }; instance C Int (()->Int) where { f=const.negate }; instance C (()->Int) Int where { f=($()) }.
leftaroundabout
4
Quelle? D'où vous est venue l'idée que typeof f (n) === 'fonction', en particulier, où n est un nombre et que vous attendez un nombre renvoyé? Je ne comprends pas comment un cas d'instance pourrait s'appliquer ici. Je ne parle pas bien Python, mais dans JS, vérifier l'argument pour un type de fonction est tout à fait faux dans ce cas. Seule la solution numérique s'applique ici. f est une fonction, f (n) est un nombre.
Harry
284

Voici une preuve de la raison pour laquelle une telle fonction ne peut pas exister, pour tous les nombres, si elle n'utilise pas d'informations supplémentaires (sauf 32 bits d'int):

Nous devons avoir f (0) = 0. (Preuve: Supposons que f (0) = x. Alors f (x) = f (f (0)) = -0 = 0. Maintenant, -x = f (f (x )) = f (0) = x, ce qui signifie que x = 0.)

De plus, pour tout xet y, supposons f(x) = y. Nous voulons f(y) = -xalors. Et f(f(y)) = -y => f(-x) = -y. Pour résumer: si f(x) = y, alors f(-x) = -y, et f(y) = -x, et f(-y) = x.

Donc, nous devons diviser tous les entiers sauf 0 en ensembles de 4, mais nous avons un nombre impair de tels entiers; non seulement cela, si nous supprimons l'entier qui n'a pas de contrepartie positive, nous avons toujours 2 nombres (mod4).

Si nous supprimons les 2 nombres maximaux restants (par valeur abs), nous pouvons obtenir la fonction:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

Bien sûr, une autre option consiste à ne pas se conformer à 0 et à obtenir les 2 numéros que nous avons supprimés en bonus. (Mais c'est juste un idiot si.)

SurDin
la source
29
Je ne peux pas croire que je devais lire cela loin pour trouver une bonne solution procédurale qui gère les nombres négatifs sans recourir à des variables globales ou des astuces qui obscurcissent le code. Si je pouvais vous voter plus d'une fois, je le ferais.
Kyle Simek
Belle observation, qu'il y a un nombre impair d'entiers non nuls dans tous les n bits signés.
Andres Jaan Tack
Ce serait ma réponse aussi, mais méfiez-vous du cas de bord n = -2147483648(valeur minimale); vous ne pouvez pas abs(n)dans ce cas, et le résultat ne sera pas défini (ou une exception).
Kirk Broadhurst
1
@ a1kmm: Désolé, -2³² ci-dessus aurait dû être -2³¹. Quoi qu'il en soit, le cas où f (0) ≠ 0 (et donc f (0) = - 2³¹) est en fait le cas le plus facile, comme nous l'avons montré, ces deux-là sont déconnectés du reste. L'autre cas que nous devons considérer est que f (0) = 0, mais f (x) = - 2³¹ pour certains x ≠ 0, x ≠ -2³¹. Dans ce cas, f (-2³¹) = f (f (x)) = - x (la note -x ne peut pas être -2³¹, car un tel x n'existe pas). Soit en outre f (-x) = y. Alors f (y) = f (f (-x)) = x. Encore une fois, y ne peut pas être -2³¹ (comme f (y) = x, mais f (-2³¹) = - x, et x n'est pas 0). Donc, -2³¹ = f (x) = f (f (y)) = - y, ce qui est impossible. Donc en effet 0 et -2³¹ doivent être déconnectés du reste (pas l'image d'autre chose).
ShreevatsaR
1
@will Il n'y a pas de zéros signés, si (comme je suppose) nous parlons d'entiers 32 bits à complément à deux.
goffrie
146

Merci à la surcharge en C ++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}
Comptrol
la source
4
Malheureusement, en raison du changement de nom, les fonctions que vous appelez "f" ont en fait des noms plus étranges.
pyon
1
J'ai pensé à quelque chose comme ça, mais en pensant à C, cela a été jeté ... bon travail!
Liran Orevi
@Rui Craverio: Cela ne fonctionnerait pas dans .NET 3.5+ parce que l'auteur a choisi d'utiliser le mot-clé var comme nom de variable.
Kredns
72
techniquement ... ce n'est pas ce que demande la question. vous avez défini 2 fonctions f (), f (int) et f (float) et la question demande "Concevoir une fonction f () ..."
elcuco
2
@elcuco Techniquement, bien sûr, mais logiquement, c'est une fonction avec plusieurs surcharges (vous pouvez faire f (f (42)) avec cela). Puisque la définition ne dit rien sur les paramètres et la valeur de retour, je peux difficilement l'accepter comme une définition technique.
Marek Toman
135

Ou, vous pourriez abuser du préprocesseur:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
Skizz
la source
Alors tu serais Konrad "Le Chiffre" Rudolph alors? Je vais chercher mon manteau. Oui, je connais toute la chose "void main", mais en ajoutant un "return 0;" est tellement d'efforts supplémentaires ;-)
Skizz
25
@Skizz, le retour 0 de main n'est pas requis en c ++ même avec une valeur de retour int ... donc en le faisant correctement, vous tapez en fait un caractère de moins!
Dan Olson
10
Skizz abuse toujours du préprocesseur: D
Arnis Lapsa
23
Ce n'est pas une fonction ... donc ce n'est pas une solution valable
smerlin
3
@smerlin: C'est techniquement une fonction inline retournant une fonction inline: les corps des deux sont développés au moment de la compilation, ou plutôt juste avant. Impossible d'être beaucoup plus efficace que cela.
Jon Purdy
103

Cela est vrai pour tous les nombres négatifs.

    f (n) = abs (n)

Parce qu'il y a un nombre négatif de plus qu'il y a de nombres positifs pour deux entiers complémentaires, f(n) = abs(n)est valable pour un cas de plus que la f(n) = n > 0 ? -n : nsolution qui est la même que f(n) = -abs(n). Je vous ai par un ...: D

MISE À JOUR

Non, ce n'est pas valable pour un cas de plus comme je viens de le reconnaître par le commentaire de litb ... abs(Int.Min)va juste déborder ...

J'ai aussi pensé à utiliser les informations du mod 2, mais j'ai conclu que cela ne fonctionne pas ... trop tôt. Si cela est fait correctement, cela fonctionnera pour tous les numéros, sauf Int.Minparce que cela débordera.

MISE À JOUR

J'ai joué avec pendant un certain temps, à la recherche d'un bon truc de manipulation, mais je n'ai pas pu trouver un joli one-liner, tandis que la solution mod 2 tient dans un.

    f (n) = 2n (abs (n)% 2) - n + sgn (n)

En C #, cela devient le suivant:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Pour le faire fonctionner pour toutes les valeurs, vous devez remplacer Math.Abs()par (n > 0) ? +n : -net inclure le calcul dans un uncheckedbloc. Ensuite, vous êtes même Int.Minmappé sur lui-même comme le fait la négation non contrôlée.

MISE À JOUR

Inspiré par une autre réponse, je vais expliquer comment fonctionne la fonction et comment construire une telle fonction.

Commençons au tout début. La fonction fest appliquée à plusieurs reprises à une valeur donnée, nce qui donne une séquence de valeurs.

    n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (f (n))))) => ...

La question demande f(f(n)) = -n, soit deux applications successives de fnier l'argument. Deux autres applications de f- quatre au total - annulent à nouveau l'argument n.

    n => f (n) => -n => f (f (f (n))) => n => f (n) => ...

Maintenant, il y a un cycle évident de longueur quatre. En substituant x = f(n)et en notant que l'équation obtenue f(f(f(n))) = f(f(x)) = -xest vraie, on obtient ce qui suit.

    n => x => -n => -x => n => ...

Nous obtenons donc un cycle de longueur quatre avec deux nombres et les deux nombres niés. Si vous imaginez le cycle comme un rectangle, les valeurs négatives sont situées aux coins opposés.

Une des nombreuses solutions pour construire un tel cycle est la suivante à partir de n.

 n => nier et soustraire un
-n - 1 = - (n + 1) => ajouter un
-n => nier et ajouter un
 n + 1 => soustraire un
 n

Un exemple concret est d'un tel cycle est +1 => -2 => -1 => +2 => +1. On a presque fini. En notant que le cycle construit contient un nombre positif impair, son successeur pair et que les deux nombres sont négatifs, nous pouvons facilement partitionner les nombres entiers en plusieurs de ces cycles ( 2^32est un multiple de quatre) et avons trouvé une fonction qui satisfait les conditions.

Mais nous avons un problème avec zéro. Le cycle doit contenir 0 => x => 0parce que zéro est annulé à lui-même. Et parce que le cycle indique déjà 0 => xqu'il suit 0 => x => 0 => x. Ce n'est qu'un cycle de longueur deux et xest transformé en lui-même après deux applications, pas en -x. Heureusement, il y a un cas qui résout le problème. Si Xest égal à zéro, nous obtenons un cycle de longueur un contenant uniquement zéro et nous avons résolu ce problème en concluant que zéro est un point fixe de f.

Terminé? Presque. Nous avons des 2^32nombres, zéro est un point fixe laissant des 2^32 - 1nombres, et nous devons partitionner ce nombre en cycles de quatre nombres. Mauvais qui 2^32 - 1n'est pas un multiple de quatre - il restera trois nombres qui ne seront dans aucun cycle de longueur quatre.

Je vais expliquer la partie restante de la solution en utilisant le plus petit ensemble de itegers signés sur 3 bits allant de -4à +3. Nous en avons fini avec zéro. Nous avons un cycle complet +1 => -2 => -1 => +2 => +1. Construisons maintenant le cycle à partir de +3.

    +3 => -4 => -3 => +4 => +3

Le problème qui se pose est qu'il +4n'est pas représentable comme un entier de 3 bits. Nous obtiendrions +4en niant -3à +3- ce qui est toujours un entier valide de 3 bits - mais en ajoutant ensuite un à +3(binaire 011), on obtient 100binaire. Interprété comme un entier non signé, il l'est, +4mais nous devons l'interpréter comme un entier signé -4. Donc, en fait, -4pour cet exemple ou Int.MinValuedans le cas général, il y a un deuxième point fixe de négation arithmétique entière - 0 et Int.MinValuesont mappés à eux-mêmes. Le cycle est donc en fait le suivant.

    +3 => -4 => -3 => -4 => -3

C'est un cycle de longueur deux et +3entre en plus dans le cycle via -4. En conséquence -4est correctement mappé sur lui-même après deux applications de fonction, +3est correctement mappé sur -3après deux applications de fonction, mais -3est mappé par erreur sur lui-même après deux applications de fonction.

Nous avons donc construit une fonction qui fonctionne pour tous les entiers sauf un. Pouvons-nous faire mieux? Non, nous ne pouvons pas. Pourquoi? Nous devons construire des cycles de longueur quatre et pouvons couvrir toute la plage entière jusqu'à quatre valeurs. Les valeurs restantes sont les deux points fixes 0et Int.MinValuequi doivent être mappés sur eux-mêmes et deux entiers arbitraires xet -xqui doivent être mappés l'un sur l'autre par deux applications de fonction.

Pour correspondre xà -xet vice versa, ils doivent former un cycle à quatre et ils doivent être situés aux coins opposés de ce cycle. En conséquence 0et Int.MinValuedoivent également être dans des coins opposés. Cela va correctement mapper xet -xmais échanger les deux points fixes 0et Int.MinValueaprès deux applications de fonction et nous laisser avec deux entrées défaillantes. Il n'est donc pas possible de construire une fonction qui fonctionne pour toutes les valeurs, mais nous en avons une qui fonctionne pour toutes les valeurs sauf une et c'est le mieux que nous puissions obtenir.

Daniel Brückner
la source
Ne répond pas aux critères: abs (abs (n))! = -N
Dan Olson
Bien sûr, pour tous les nombres négatifs, comme il l'a dit. Cela faisait partie de la question: si vous ne pouvez pas en trouver un général, trouvez-en un qui fonctionne pour la gamme la plus large possible.
jalf
Cette réponse est au moins aussi bonne que la réponse de Marj Synowiec et Rowland Shaw, elle ne fonctionne que pour une plage de nombres différente
1800 INFORMATION
19
Mec, tu peux aussi bien te débarrasser des "MISES À JOUR" et écrire une seule réponse cohérente. Le bas 3/4 ("inspiré par une autre réponse") est génial.
Andres Jaan Tack
1
J'aime vraiment la solution abs pour les nombres négatifs. Simple et facile à comprendre.
Thorbjørn Ravn Andersen
97

À l'aide de nombres complexes, vous pouvez efficacement diviser la tâche de négation d'un nombre en deux étapes:

  • multipliez n par i, et vous obtenez n * i, qui est n tourné de 90 ° dans le sens antihoraire
  • multipliez à nouveau par i, et vous obtenez -n

La grande chose est que vous n'avez pas besoin de code de traitement spécial. La simple multiplication par i fait le travail.

Mais vous n'êtes pas autorisé à utiliser des nombres complexes. Vous devez donc en quelque sorte créer votre propre axe imaginaire, en utilisant une partie de votre plage de données. Étant donné que vous avez besoin d'autant de valeurs imaginaires (intermédiaires) que de valeurs initiales, il ne vous reste que la moitié de la plage de données.

J'ai essayé de visualiser cela sur la figure suivante, en supposant que les données signées 8 bits. Vous devez mettre cela à l'échelle pour les entiers 32 bits. La plage autorisée pour n initial est de -64 à +63. Voici ce que fait la fonction pour n positif:

  • Si n est dans 0..63 (plage initiale), l'appel de fonction ajoute 64, mappant n à la plage 64..127 (plage intermédiaire)
  • Si n est dans 64..127 (plage intermédiaire), la fonction soustrait n de 64, mappant n à la plage 0 ..- 63

Pour n négatif, la fonction utilise la plage intermédiaire -65 ..- 128.

texte alternatif

geschema
la source
4
@geschema, quel outil avez-vous utilisé pour créer ces jolis graphismes?
jwfearn
10
Désolé, la question dit explicitement pas de nombres complexes.
Rui Craveiro
6
@Liran: J'ai utilisé OmniGraffle (Mac uniquement)
geschema
39
+1 Je pense que c'est la meilleure réponse. Je ne pense pas que les gens lisent suffisamment, car ils ont tous noté que la question disait que les nombres complexes ne pouvaient pas être utilisés. J'ai lu le tout et vous avez décrit la solution en nombres complexes pour préparer le terrain pour la solution non complexe à la question posée. Très bien fait.
jrista
1
@jrista toutes les solutions utilisent une deuxième dimension, qui est tout ce que sont réellement les «nombres complexes» (la plupart utilisent des impairs vs pairs, et ci-dessus utilise floatvs int). L '«anneau à 4 éléments» que de nombreuses réponses décrivent nécessite 4 états, qui peuvent être représentés comme 2 dimensions avec chacun 2 états. Le problème avec cette réponse est qu'elle nécessite un espace de traitement supplémentaire (ne fonctionne que pour -64..63, mais a besoin de -128..127) et ne précise pas explicitement la formule écrite!
Kirk Broadhurst
65

Fonctionne sauf int.MaxValue et int.MinValue

    public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

pictural

Rodrick Chapman
la source
Je ne sais pas pourquoi cela a été rejeté. Pour quelles entrées échoue-t-il?
Rodrick Chapman
Pourquoi n'utilisez-vous pas la fonction signum?!?
comonad
1
L'image est vraiment bonne. Envoyer 0à 0et -2147483648à -2147483648étant donné que ces deux nombres sont des points fixes pour l'opérateur de négation, x => -x. Pour le reste des nombres, suivez les flèches dans l'image ci-dessus. Comme il ressort clairement de la réponse de SurDin et de ses commentaires, il y aura deux nombres, dans ce cas 2147483647et -2147483647sans autre paire à échanger.
Jeppe Stig Nielsen
Il ressemble à un smiley - avec beaucoup de rides
Anshul
48

La question ne dit rien sur ce que le type d'entrée et de la valeur de retour de la fonction fdoivent être (au moins pas la façon dont vous l'avez présenté) ...

... juste que lorsque n est un entier 32 bits, f(f(n)) = -n

Alors, que diriez-vous de quelque chose comme

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

Si n est un entier 32 bits, alors l'instruction f(f(n)) == -nsera vraie.

De toute évidence, cette approche pourrait être étendue pour fonctionner avec une gamme de nombres encore plus large ...

Daniel LeCheminant
la source
2
Sournois. Limite de caractères.
Joe Phillips
2
Ouais, je travaillais sur une approche similaire. Mais tu m'as battu. +1 :)
jalf
1
Très intelligent! Ceci est très proche (et en fait le même que) d'utiliser des nombres complexes, ce qui serait la solution évidente et idéale mais elle est explicitement interdite. Travailler en dehors de la plage de nombres autorisés.
Kirk Broadhurst
48

pour le javascript (ou d'autres langages typés dynamiquement), vous pouvez demander à la fonction d'accepter un int ou un objet et de renvoyer l'autre. c'est à dire

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

donnant

js> f(f(10))  
-10
js> f(f(-10))
10

vous pouvez également utiliser la surcharge dans un langage fortement typé bien que cela puisse enfreindre les règles, c.-à-d.

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}
cobbal
la source
Ce dernier ne signifie pas l'exigence d'une fonction "a" (singulière). :)
Drew
Retirez la deuxième moitié de la réponse et c'est une bonne réponse.
jmucchiello le
@Drew, c'est pourquoi j'ai mentionné que cela pouvait enfreindre les règles
cobbal
2
En JavaScript, une fonction est un objet et peut donc conserver un état.
Nosredna
1
IMO: fonction f (n) {return n.passed? -n.val: {val: n, passé: 1}} est plus lisible et plus court.
SamGoody
46

Selon votre plateforme, certaines langues vous permettent de conserver l'état dans la fonction. VB.Net, par exemple:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

L'IIRC, C ++ l'a également autorisé. Je soupçonne cependant qu'ils recherchent une solution différente.

Une autre idée est que, puisqu'ils n'ont pas défini le résultat du premier appel à la fonction, vous pouvez utiliser impair / égalité pour contrôler s'il faut inverser le signe:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

Ajoutez un à la magnitude de tous les nombres pairs, soustrayez un de la magnitude de tous les nombres impairs. Le résultat de deux appels a la même ampleur, mais le seul appel où il est même nous échangeons le signe. Il y a des cas où cela ne fonctionnera pas (-1, max ou min int), mais cela fonctionne beaucoup mieux que tout ce qui a été suggéré jusqu'à présent.

Joel Coehoorn
la source
1
Je pense que cela fonctionne pour MAX_INT car c'est toujours étrange. Cela ne fonctionne pas pour MIN_INT et -1.
Airsource Ltd
9
Ce n'est pas une fonction si elle a des effets secondaires.
nos
12
C'est peut-être vrai en mathématiques, mais ce n'est pas pertinent en programmation. La question est donc de savoir s'ils recherchent une solution mathématique ou une solution de programmation. Mais étant donné que c'est pour un travail de programmation ...
Ryan Lundy
+1 J'allais en poster un avec en C avec "static int x" implémentant un FIFO avec négation de la sortie. Mais c'est assez proche.
phkahler
2
@nos: Oui, ce n'est tout simplement pas référentiellement transparent.
Clark Gaebel
26

Exploiter les exceptions JavaScript.

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(1)) => -1

Anurag
la source
Je doute que des exceptions aient été utilisées comme ça avant ... :)
NoBugs
+1 Pensée prête à l'emploi. Cool! Mais dans le code de production, j'utiliserais typeof juste pour être sûr.
21

Pour toutes les valeurs 32 bits (avec la mise en garde de -0 à -2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

Vous devez essentiellement associer chaque boucle -x => x => -x à la boucle ay => -y => y. J'ai donc jumelé les côtés opposés du split.

par exemple pour les entiers 4 bits:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
2 tours
la source
21

Une version C ++, probablement pliant quelque peu les règles mais fonctionne pour tous les types numériques (flottants, entiers, doubles) et même les types de classe qui surchargent le moins unaire:

template <class T>
struct f_result
{
  T value;
};

template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}

template <class T>
T f (f_result <T> n)
{
  return -n.value;
}

void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}
Skizz
la source
Bonne idée. Comme alternative, vous pourriez probablement perdre la structure et à la place avoir une fonction retourner un pointeur, l'autre fonction déréférencer et annuler.
Imbue
20

x86 asm (style AT&T):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

Code vérifié, tous les entiers 32 bits possibles passés, erreur avec -2147483647 (sous-dépassement).

LiraNuna
la source
19

Utilise les globaux ... mais alors?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}
teeks99
la source
3
Pas sûr que c'était l'intention du poseur de question, mais +1 pour "sortir des sentiers battus".
Liran Orevi
5
Au lieu de dire conditionnellement "done = true", vous devriez toujours dire "done =! Done", de cette façon, votre fonction peut être utilisée plusieurs fois.
Chris Lutz
@Chris, puisque la définition de done sur true est à l'intérieur d'un bloc if (! Done), c'est équivalent à done =! Done, mais! Done n'a pas besoin d'être calculé (ou optimisé par le compilateur, s'il est assez intelligent) .
nsayer
1
Ma première pensée a également été de résoudre ce problème en utilisant une variable globale, même si cela ressemblait à de la triche pour cette question particulière. Je dirais cependant qu'une solution de variable globale est la meilleure solution compte tenu des spécifications de la question. L'utilisation d'un global permet de comprendre très facilement ce qui se passe. Je serais d'accord pour dire qu'un done! = Done serait mieux. Déplacez simplement cela en dehors de la clause if.
Alderath
3
Techniquement, tout ce qui maintient l'état n'est pas une fonction, mais une machine d'état. Par définition , une fonction donne toujours la même sortie pour la même entrée.
Ted Hopp
19

Cette solution Perl fonctionne pour les entiers, les flottants et les chaînes .

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

Essayez quelques données de test.

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

Production:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
FMc
la source
Mais ça ne le garde pas int. Vous stockez essentiellement des données de variables globales dans l'int "n" lui-même ... sauf que ce n'est pas un int sinon vous ne pourriez pas le faire. Par exemple, si nc'était une chaîne que je pourrais faire, 548 devient "First_Time_548", puis la prochaine fois qu'il passe par la fonction ... if (prefix == First_Time_ ") remplace" First_Time_ "par" - "
Albert Renshaw
@AlbertRenshaw Je ne sais pas où vous obtenez ces idées. (1) Il n'y a certainement aucune variable globale impliquée ici. (2) Si vous donnez à la fonction un int, vous obtiendrez un int - ou une référence à un int, si vous appelez la fonction un nombre impair de fois. (3) Peut-être plus fondamentalement, c'est Perl . À toutes fins pratiques, les pouces et les cordes sont entièrement interchangeables. Les chaînes qui aiment ressembler à des nombres fonctionneront parfaitement bien comme des nombres dans la plupart des contextes, et les nombres se satureront volontiers chaque fois qu'on leur demandera.
FMc
Désolé, je ne sais pas grand chose, il semble que vous utilisiez un tableau global haha
Albert Renshaw
18

Personne n'a jamais dit que f (x) devait être du même type.

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2
Composez Z
la source
16

Je n'essaie pas réellement de donner une solution au problème lui-même, mais j'ai quelques commentaires, car la question indique que ce problème a été posé faisait partie d'un entretien (d'emploi?):

  • Je voudrais d'abord demander "Pourquoi une telle fonction serait-elle nécessaire? Quel est le plus gros problème dont cela fait partie?" au lieu d'essayer de résoudre le problème posé sur place. Cela montre comment je pense et comment je m'attaque à des problèmes comme celui-ci. Qui sait? C'est peut-être même la raison pour laquelle la question est posée en premier lieu lors d'un entretien. Si la réponse est "Ça ne vous dérange pas, supposez que c'est nécessaire et montrez-moi comment vous concevriez cette fonction." Je continuerais alors à le faire.
  • Ensuite, j'écrirais le code de cas de test C # que j'utiliserais (l'évidence: boucle de int.MinValueà int.MaxValue, et pour chacun ndans cet appel de plage f(f(n))et vérifier le résultat est-n ), en disant que j'utiliserais ensuite Test Driven Development pour arriver à une telle fonction.
  • Ce n'est que si l'intervieweur continue de me demander de résoudre le problème posé que je commencerai à essayer de griffonner le pseudocode pendant l'entretien lui-même pour essayer d'obtenir une sorte de réponse. Cependant, je ne pense pas vraiment que je serais en train de sauter pour prendre le poste si l'intervieweur pouvait être une indication de la société.

Oh, cette réponse suppose que l'entrevue était pour un poste lié à la programmation C #. Ce serait bien sûr une réponse idiote si l'entretien était pour un poste lié aux mathématiques. ;-)

peSHIr
la source
7
Vous avez de la chance qu'ils aient demandé 32 int, si c'était 64 bits, l'interview ne se poursuivra jamais après avoir exécuté les tests ;-)
alex2k8
En effet, si j'arrivais à un point d'écrire ce test et de le lancer lors d'une interview. ;-) Mon point: j'essaierais de ne pas arriver à ce point dans une interview du tout. La programmation est plus "une façon de penser" que "comment écrit-il des lignes de code" à mon avis.
peSHIr
7
Ne suivez pas ces conseils lors d'un véritable entretien. L'intervieweur attend de vous que vous répondiez réellement à la question. Remettre en question la pertinence de la question ne vous procurera rien, mais cela peut ennuyer l'intervieweur. Concevoir un test trivial ne vous rapproche pas de la réponse, et vous ne pouvez pas l'exécuter dans l'interview. Si vous obtenez des informations supplémentaires (32 bits), essayez de comprendre comment cela pourrait être utile.
Stefan Haustein
Un intervieweur qui s'énerve lorsque je demande plus d'informations (tout en remettant éventuellement en question la pertinence de sa question dans le processus) n'est pas un intervieweur avec lequel je veux nécessairement travailler. Je vais donc continuer à poser des questions comme ça dans les interviews. S'ils ne l'aiment pas, je terminerai probablement l'interview pour arrêter de perdre plus de temps à la fois. Je n'aime pas l'esprit "Je ne faisais que suivre les ordres". Le faites vous..?
peSHIr
16

Je voudrais que vous changiez les 2 bits les plus significatifs.

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

Comme vous pouvez le voir, ce n'est qu'un ajout, en laissant de côté le peu porté.

Comment ai-je obtenu la réponse? Ma première pensée était juste un besoin de symétrie. 4 tours pour revenir là où j'ai commencé. Au début, je pensais que c'était du code Gray à 2 bits. Ensuite, j'ai pensé que le binaire standard était suffisant.

eipipuz
la source
Le problème avec cette approche est qu'elle ne fonctionne pas avec les nombres négatifs du compliment à deux (ce que tous les processeurs modernes utilisent). C'est pourquoi j'ai supprimé ma réponse identique.
Tamas Czinege
La question spécifiait des entiers signés 32 bits. Cette solution ne fonctionne pas pour les représentations à complément à deux ou à complément à un des entiers signés 32 bits. Cela ne fonctionnera que pour les représentations de signe et d'amplitude, qui sont très rares dans les ordinateurs modernes (autres que les nombres à virgule flottante).
Jeffrey L Whitledge
1
@DrJokepu - Wow, après six mois - jinx!
Jeffrey L Whitledge
N'avez-vous pas simplement besoin de convertir les nombres en représentation de signe et d'amplitude à l'intérieur de la fonction, d'effectuer la transformation, puis de reconvertir en quelle que soit la représentation entière native avant de la renvoyer?
Bill Michell
J'aime que vous ayez essentiellement implémenté des nombres complexes en introduisant un bit imaginaire :)
jabirali
16

Voici une solution qui s'inspire de l'exigence ou de la revendication selon laquelle les nombres complexes ne peuvent pas être utilisés pour résoudre ce problème.

La multiplication par la racine carrée de -1 est une idée qui semble échouer car -1 n'a pas de racine carrée sur les entiers. Mais jouer avec un programme comme mathématique donne par exemple l'équation

(1849436465 2 +1) mod (2 32 -3) = 0.

et c'est presque aussi bon que d'avoir une racine carrée de -1. Le résultat de la fonction doit être un entier signé. Je vais donc utiliser une opération modulo modifiée mods (x, n) qui retourne l'entier y congruent à x modulo n qui est le plus proche de 0. Seuls très peu de langages de programmation ont réussi une opération modulo, mais elle peut facilement être définie . Par exemple en python c'est:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

En utilisant l'équation ci-dessus, le problème peut maintenant être résolu comme

def f(x):
    return mods(x*1849436465, 2**32-3)

Cela satisfait f(f(x)) = -xpour tous les entiers de la plage[-231-2, 231-2] . Les résultats de f(x)sont également dans cette plage, mais bien sûr, le calcul aurait besoin d'entiers 64 bits.

Accipitridae
la source
13

C # pour une plage de 2 ^ 32 - 1 nombres, tous les nombres int32 sauf (Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

impressions:

2147483647
3
2
1
0
-1
-2
-3
-2147483647
Pop Catalin
la source
Cela ne fonctionne pas non plus pour f (0) qui est 1073741824. f (1073741824) = 0. f (f (1073741824)) = 1073741824
Dinah
Vous pouvez généralement prouver que pour un type entier complément à deux de n'importe quelle taille de bit, la fonction ne doit pas fonctionner pour au moins deux valeurs d'entrée.
slacker
12

La fonction doit essentiellement diviser la plage disponible en cycles de taille 4, avec -n à l'extrémité opposée du cycle de n. Cependant, 0 doit faire partie d'un cycle de taille 1, car sinon0->x->0->x != -x . Parce que 0 est seul, il doit y avoir 3 autres valeurs dans notre plage (dont la taille est un multiple de 4) pas dans un cycle correct avec 4 éléments.

J'ai choisi ces valeurs étranges supplémentaires pour être MIN_INT, MAX_INTet MIN_INT+1. En outre, MIN_INT+1sera mappé MAX_INTcorrectement, mais restez bloqué et ne mappez pas en arrière. Je pense que c'est le meilleur compromis, car il a la belle propriété de ne fonctionner que correctement les valeurs extrêmes. Cela signifie également que cela fonctionnerait pour tous les BigInts.

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)
Strilanc
la source
12

Personne n'a dit qu'il devait être apatride.

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

Tricher, mais pas autant que beaucoup d'exemples. Encore plus de mal serait de jeter un œil à la pile pour voir si l'adresse de votre appelant est & f, mais cela sera plus portable (bien que pas sûr pour les threads ... la version thread-safe utiliserait TLS). Encore plus de mal:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

Bien sûr, ni l'un ni l'autre ne fonctionne trop bien dans le cas de MIN_INT32, mais vous ne pouvez pas faire grand-chose à ce sujet, sauf si vous êtes autorisé à renvoyer un type plus large.

Christopher Smith
la source
vous pouvez le «mettre à niveau» pour demander l'adresse (oui, vous devez l'obtenir par ref \ comme pointeur) - en C, par exemple: int f (int & n) {static int * addr = & n; if (addr == & n) {return -n; } return n; }
IUnknownPointer
11

Je pourrais imaginer utiliser le 31e bit comme un bit imaginaire ( i ) serait une approche qui prendrait en charge la moitié de la plage totale.

llamaoo7
la source
Ce serait plus complexe mais pas plus efficace que la meilleure réponse actuelle
1800 INFORMATION
1
@ 1800 INFORMATION: Par contre, le domaine [-2 ^ 30 + 1, 2 ^ 30-1] est contigu ce qui est plus attrayant d'un point de vue mathématique.
Jochen Walter
10

fonctionne pour n = [0 .. 2 ^ 31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}
MartinStettner
la source
10

Le problème indique "des entiers signés 32 bits" mais ne spécifie pas s'ils sont à deux ou à un complément .

Si vous utilisez le complément à un, toutes les valeurs de 2 ^ 32 se produisent par cycles de longueur quatre - vous n'avez pas besoin d'un cas spécial pour zéro, et vous n'avez pas non plus besoin de conditions.

En C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

Cela fonctionne par

  1. Échange des blocs haut et bas 16 bits
  2. Inverser l'un des blocs

Après deux passes, nous avons l'inverse au niveau du bit de la valeur d'origine. Ce qui dans la représentation du complément à un équivaut à la négation.

Exemples:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)
finnw
la source
1
Qu'en est-il de l'ordre des octets sur différentes architectures?
Steven
1
Toute l'arithmétique est de 32 bits. Je ne manipule pas d'octets individuels, donc l'ordre des octets ne l'affectera pas.
finnw
Cela semble assez proche. Vous pouvez supposer que l'entrée est à 2 compléments. Vous vous convertissez donc en représentation du bit de signe. Maintenant, selon le dernier bit, vous retournez le premier bit et le dernier bit ou juste le dernier bit. Fondamentalement, vous annulez uniquement les nombres pairs et faites un cycle pair / impair tout le temps. Vous revenez donc d'impaire à impair et même à même après 2 appels. À la fin, vous vous reconvertissez en 2-complément. J'ai affiché le code pour cela quelque part ci-dessous.
Stefan Haustein
9

:RÉ

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
A dessiné
la source
5
Pourrait également vous faire discuter de la raison pour laquelle les variables globales sont mauvaises si elles ne vous excluent pas de l'entretien juste là!
palswim
9
return x ^ ((x%2) ? 1 : -INT_MAX);
Mike Meehan
la source
7

J'aimerais partager mon point de vue sur ce problème intéressant en tant que mathématicien. Je pense que j'ai la solution la plus efficace.

Si je me souviens bien, vous annulez un entier 32 bits signé en retournant simplement le premier bit. Par exemple, si n = 1001 1101 1110 1011 1110 0000 1110 1010, alors -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Alors, comment définissons-nous une fonction f qui prend un entier signé 32 bits et renvoie un autre entier signé 32 bits avec la propriété que prendre deux fois f équivaut à retourner le premier bit?

Permettez-moi de reformuler la question sans mentionner les concepts arithmétiques comme les nombres entiers.

Comment définir une fonction f qui prend une séquence de zéros et de longueur 32 et renvoie une séquence de zéros et de même longueur, avec la propriété que prendre f deux fois équivaut à retourner le premier bit?

Observation: Si vous pouvez répondre à la question ci-dessus pour le cas 32 bits, vous pouvez également répondre pour le cas 64 bits, le cas 100 bits, etc. Vous appliquez simplement f au premier 32 bits.

Maintenant, si vous pouvez répondre à la question du cas 2 bits, Voila!

Et oui, il s'avère que changer les 2 premiers bits est suffisant.

Voici le pseudo-code

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

Remarque: L'étape 2 et l'étape 3 ensemble peuvent être résumées comme (a, b) -> (-b, a). Ça vous semble familier? Cela devrait vous rappeler la rotation de 90 degrés de l'avion et la multiplication par la racine carrée de -1.

Si je venais de présenter le pseudo-code seul sans le long prélude, cela ressemblerait à un lapin sorti du chapeau, je voulais expliquer comment j'ai obtenu la solution.

Yoo
la source
6
Oui, c'est un problème intéressant. Tu connais tes maths. Mais c'est un problème informatique. Vous devez donc étudier les ordinateurs. La représentation de l'ampleur des signes est autorisée, mais elle est devenue démodée il y a environ 60 ans. Le complément à 2 est le plus populaire.
Programmeur Windows
5
Voici ce que fait votre fonction sur les deux bits lorsqu'elle est appliquée deux fois: (a, b) -> (-b, a) -> (-a, -b). Mais nous essayons d'accéder à (-a, b), pas à (-a, -b).
buti-oxa
@ buti-oxa, vous avez raison. L'opération sur deux bits devrait se dérouler comme suit: 00 -> 01 -> 10 -> 11 -> 00. Mais alors mon algorithme suppose une représentation en amplitude de signe qui est impopulaire maintenant, comme l'a dit le programmeur Windows, donc je pense que mon algorithme est de peu d'utilité .
Yoo
Alors, ne peut-il pas simplement faire les étapes deux fois au lieu d'une fois?
Nosredna
4
buti-oxa a tout à fait raison: la fonction ne retourne même pas le premier bit après deux invocations, elle retourne les deux premiers bits. Renverser tous les bits est plus proche de ce que fait le complément à 2, mais ce n'est pas tout à fait vrai.
redtuna