Designing function f(f(n)) == -n

Question

我上次面试时收到的一个问题：

设计一个函数f，使得：

f(f(n)) == -n

当 n 是一个32位的有符号整数时，你不能使用复数运算。

如果你不能为所有数字范围设计这样的函数，那就尽可能地为最大范围设计。

有什么想法吗？

- Hrvoje Prgeša

---

这次面试是为了什么职位？ - tymtam

Answer 1

您没有说明他们期望的是什么类型的语言...这里是一个静态解决方案（Haskell）。它基本上是通过操纵最高有效位和次高有效位来实现的：

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

在动态语言（如Python）中操作会更加容易。只需要检查参数是否为数字X，然后返回一个返回-X的lambda函数：

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

- viraptor

---

酷，我喜欢这个......在JavaScript中采用相同的方法：var f = function(n) { return (typeof n == 'function') ? n() : function() { return -n; } } - Mark Renouf

普通的面试官会知道 Lambda 表达式是什么吗？ - Jeremy Powell

@Alex Bagnolini - 可能不行 - 如果没有使用 "dynamic"，你不能拥有一个可以编译的 "int 或 Func<int>" 返回类型。 - viraptor

当然，在 Haskell 中也可以使用这种类型欺骗技巧，尽管它是静态的：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

什么？你从哪里得出了 typeof f(n) === 'function' 的想法，特别是当 n 是一个数字并且你期望返回一个数字时？我不明白为什么实例化的情况会适用于这里。我不太懂 Python，但在 JS 中检查函数类型的参数在这种情况下是完全错误的。只有数字解决方案适用于这里。f 是一个函数，f(n) 是一个数字。 - Harry

Answer 2

f(n) = math.copysign(1, n) - (-1)**n * n

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会自动将整数提升为任意长度的长整型。在其他语言中，最大的正整数将溢出，因此它适用于除了最大的正整数以外的所有整数。

---

要使其适用于实数，您需要将 (-1)ⁿ 中的 n 替换为 { ceiling(n) if n>0; floor(n) if n<0 }。

在 C# 中（适用于任何 double 类型，但排除溢出情况）：

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

---

对于-1来说是错误的，因为-1*0仍然是0。 - Joel Coehoorn

不是这样的。f(-1) = 0。f(0) = 1。 - 1800 INFORMATION

但是对于1来说，它是有问题的。f(1) = 0，f(0) = 1。 - 1800 INFORMATION

嗯，用奇数和偶数保存状态，我本应该想到这一点。 - Unknown

我认为最重要的不是实际函数本身（有无限多种解决方案），而是你能构建这样一个函数的过程。 - isekaijin

Answer 3

这是为什么如果不使用额外的信息（除了int的32位），这样的函数为所有数字不存在的证明：

我们必须有f(0) = 0。（证明：假设f(0) = x。那么f(x) = f(f(0)) = -0 = 0。现在，-x = f(f(x)) = f(0) = x，这意味着x = 0。）

进一步地，对于任何x和y，假设f(x) = y。我们希望f(y) = -x。然后，f(f(y)) = -y => f(-x) = -y。总之，如果f(x) = y，则f(-x) = -y，f(y) = -x，且f(-y) = x。

因此，我们需要将所有整数（除了0）分成四组，但是我们有奇数个这样的整数。不仅如此，如果我们移除没有正对应数的整数，我们仍然有2(mod4)个数。

如果我们删除剩下的两个最大数（按绝对值），我们可以得到这个函数：

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);
    }
}   

当然，另一种选择是不为0进行计算，然后把我们删掉的那两个数作为奖励。（但这只是一个愚蠢的假设。）

- SurDin

---

我不敢相信我得往下读这么远才找到一个好的流程解决方案，可以处理负数而不需要使用全局变量或使代码难以理解的技巧。如果我可以投多次票给你，我会这样做的。 - Kyle Simek

这也是我的答案，但要注意边界情况 n = -2147483648（最小值）; 在这种情况下，您不能对 n 取绝对值，结果将是未定义的（或异常）。 - Kirk Broadhurst

@a1kmm：抱歉，-2³²应该是-2³¹。无论如何，当f(0)≠0（因此f(0)=-2³¹）时，这种情况实际上是更容易的情况，因为我们已经证明了这两种情况与其余情况是不相关的。我们需要考虑的另一种情况是f(0)=0，但是对于某些x≠0，x≠-2³¹，有f(x)=-2³¹。在这种情况下，f(-2³¹)=f(f(x))=-x（请注意，-x不能是-2³¹，因为不存在这样的x）。进一步地，让f(-x)=y。然后f(y)=f(f(-x))=x。同样，y不能是-2³¹（因为f(y)=x，但是f(-2³¹)=-x，而x不是0）。因此，-2³¹=f(x)=f(f(y))=-y，这是不可能的。因此，确实存在0和-2³¹必须与其余部分（而不是其他任何东西的图像）断开连接。 - ShreevatsaR

我必须在这个问题上不同意你的看法。你所需要做的就是将输入的整数转换为位数组（如果编程语言允许，也可以直接读取为位数组），然后根据符号位将它们分组成一对对的数字，然后选择另一个位 - 无论哪一个都可以 - 然后循环遍历它们。但是，这只有在编程语言允许有符号零时才有效。 - will

@will 如果我们谈论的是二进制补码32位整数，那么就没有带符号的零。 - goffrie

Answer 4

由于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));
}

- Özgür

---

很遗憾，由于名称混淆，你所调用的“f”函数实际上有着更奇怪的名称。 - isekaijin

我也曾想过这样的事情，但是考虑到使用C语言的话，就被放弃了……做得好！ - Liran Orevi

@Rui Craverio：在.NET 3.5+中无法工作，因为作者选择使用var关键字作为变量名。 - Kredns

技术上来说，这不是问题要求的。你定义了2个f()函数，f(int)和f(float)，而问题要求“设计一个函数f()...” - elcuco

从技术上讲，当然可以，但从逻辑上讲，这是一个带有多个重载的函数（你可以使用它来做 f(f(42))）。由于这个定义没有涉及参数和返回值，我很难将其接受为技术定义。 - Mark Toman

Answer 5

或者，您可以滥用预处理器：

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

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

- Skizz

---

那么你就是Konrad "Le Chiffre" Rudolph？我要去拿我的外套了。是的，我知道关于“void main”的整个事情，但添加“return 0;”只是多余的努力;-) - Skizz

即使在 C++ 中有整数返回值，从主函数返回0也不是必需的。因此，通过正确的做法，实际上你可以少输入一个字符！ - Dan Olson

Skizz总是滥用预处理器 :D - Arnis Lapsa

这不是一个函数，因此这不是一个有效的解决方案。 - smerlin

这实际上是一个返回内联函数的内联函数：两个函数的主体在编译时或者说是在编译前被展开。效率不可能再高了。 - Jon Purdy

Answer 6

这对所有负数都成立。

    f(n) = abs(n)

对于二进制补码整数，负数比正数多一个，因此 f(n) = abs(n) 比 f(n) = n > 0 ? -n : n 多适用一种情况，而后者与 f(n) = -abs(n) 相同。恰好多了一种情况... :D

更新

不，它并不比 litb 的评论更适用于一种情况...abs(Int.Min) 将会溢出...

我也考虑过使用模 2 信息，但得出结论：不可行...还为时过早。如果正确实现，它将适用于除 Int.Min 以外的所有数字，因为这个将会溢出。

更新

我试着找一个好的位操作技巧，但是我没有找到一个漂亮的单行代码，而模 2 解决方案则可以在一行内完成。

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

在 C# 中，则变成以下代码：

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

为了使其适用于所有值，您必须将 Math.Abs() 替换为 (n > 0) ? +n : -n 并将计算包含在一个 unchecked 块中。这样，未经检查的取反操作就可以使Int.Min映射到自身。 更新 受到另一篇答案的启发，我将解释函数如何工作以及如何构造这样的函数。

让我们从最开始说起。函数f反复应用于给定值n，产生一系列值。

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

问题要求f(f(n))=-n，即对f的两次连续应用将参数取反。再应用两次f（总共四次），又会将参数取反得到n。

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

现在有一个明显的长度为四的循环。将x=f(n)代入，并注意等式 f(f(f(n)))=f(f(x))=-x 成立，则得到以下结果。

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

因此，我们得到了一个长度为四的循环，其中包含两个数字和这两个数字的反向值。如果你将这个循环想象成一个矩形，那么取反的值就位于对角线上。

从n开始，有许多解决方案可以构造这样的周期。

 n                 => 取反并减一
-n - 1 = -(n + 1)  => 加一
-n                 => 取反并加一
 n + 1             => 减一
 n

一个具体的例子是这样一个循环：+1 => -2 => -1 => +2 => +1。我们已经快完成了。注意到构造的循环包含一个奇正数、它的偶数后继以及这两个数的相反数，我们可以轻松地将整数分成许多这样的循环（2^32 是四的倍数），并找到满足条件的函数。

但是我们在零上有问题。循环必须包含 0 => x => 0，因为零被取反为它本身。而且因为循环状态已经是 0 => x，所以得到 0 => x => 0 => x。这只是一个长度为二的循环，x在两次应用后变成它本身，而不是变成 -x。幸运的是，有一种情况可以解决这个问题。如果 X 等于零，我们得到一个长度为一的循环，只包含零，我们解决了这个问题，得出零是 f 的一个固定点。

完成了吗？几乎了。我们有 2^32 个数字，零是一个固定点，留下 2^32 - 1 个数字，我们必须将这个数字分成长度为四的循环。不好的是，2^32 - 1 不是四的倍数——还剩下三个数字不在任何长度为四的循环中。

我将用范围从 -4 到 +3 的三位有符号整数的更小集合来解释解决方案的其余部分。我们已经处理完了零。我们有一个完整的循环 +1 => -2 => -1 => +2 => +1。现在让我们构造以 +3 开始的循环。问题是 +4 不能被表示为3位整数。我们可以通过将 -3 变为 +3（仍然是一个有效的3位整数），然后将1加到 +3（二进制 011），得到 100 作为无符号整数是 +4，但我们必须将其解释为有符号整数 -4。因此，实际上这个例子中的答案是 -4 或者一般情况下的 Int.MinValue 是整数算术否定的第二个固定点 - 0 和 Int.MinValue 映射到它们自己。因此，循环实际上如下所示。

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

这是一个长度为2的循环，并且另外一个 +3 通过 -4 进入该循环。结果是在两个函数应用后，-4 正确地映射到自身，+3 在两个函数应用后正确映射到 -3，但 -3 在两个函数应用后错误地映射到自身。

因此，我们构造了一个对所有整数都有效，但有一个整数无效的函数。我们能做得更好吗？不行。为什么？我们必须构造长度为四的循环，并且能覆盖整个整数范围达到四个值。剩下的值是两个固定点 0 和 Int.MinValue，它们必须映射到自身，并且两个任意整数 x 和 -x 必须通过两个函数应用相互映射。为将 x 映射到 -x 以及将其反过来，它们必须形成一个四边形循环，并且必须位于该循环的对角处。因此，0 和 Int.MinValue 也必须位于对角位置。这将正确地映射 x 和 -x，但在两次函数应用后交换两个固定点 0 和 Int.MinValue，并留下两个失败的输入。因此，无法构建适用于所有值的函数，但我们有一个适用于除一个值之外的所有值的函数，这是我们能够达到的最好结果。

- Daniel Brückner

---

不符合条件：abs(abs(n)) != -n - Dan Olson

兄弟，你最好删掉“更新”部分，只写一个连贯正确的答案。后面三分之四的部分（“灵感来自另一个回答”）非常棒。 - Andres Jaan Tack

我真的很喜欢对于负数的绝对值解决方案。简单易懂。 - Thorbjørn Ravn Andersen

我相当确定你可以通过（至少这是我的想法）在大小为2 ^ b-2的群组中操作，而不是在大小为2 ^ b的群组中操作（这就是你之前所做的）。这样可以使你的函数适用于零。 - Alex R

@AndresJaanTack：感谢您的评论。我之前没有读过底部的四分之三。 - serv-inc

Answer 7

使用复数，你可以将取反一个数字的任务有效地分为两步:

• 将n乘以i，得到n*i，这是向左旋转90°的n
• 再次乘以i，得到-n

很棒的是，你不需要任何特殊的处理代码。只需乘以i即可完成任务。

但是，如果不允许使用复数，则必须使用部分数据范围来创建自己的虚数轴。由于你需要与初始值一样多的虚数（中间）值，因此只剩下一半的数据范围。

我试图在以下图表上可视化它，假设签名8位数据。您需要针对32位整数进行缩放。 初始n的允许范围为-64到+63。以下是正n的函数执行情况：

• 如果n在0..63之间（初始范围），函数调用将64添加，将n映射到范围64..127（中间范围）
• 如果n在64..127之间（中间范围），函数从64中减去n，将n映射到范围0..-63

对于负n，该函数使用中间范围-65..-128。

- geschema

---

@geschema，你用了什么工具制作出那些漂亮的图形？ - jwfearn

抱歉，问题明确表示不允许使用复数。 - Rui Craveiro

@Liran: 我使用的是OmniGraffle（仅适用于Mac）。 - geschema

我认为这是最佳答案。我觉得人们没有阅读足够多的内容，因为他们都注意到问题中提到不能使用复数。我把整个内容都仔细读了一遍，你用复数描述解决方案，为了引出非复数解答该问题。做得非常好。 - jrista

@jrista 所有的解决方案都使用了第二维度，这正是“复数”的本质（大多数使用奇偶性，而上面使用float与int）。许多答案描述的“4元环”需要4个状态，可以表示为2个状态的每个维度。这个答案的问题在于它需要额外的处理空间（仅适用于-64..63，但需要-128..127的空间），并且没有明确说明书面公式！ - Kirk Broadhurst

Answer 8

适用于除 int.MaxValue 和 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));
    }

- Rodrick Chapman

---

不确定为什么这个被踩了。它在哪些输入下失败了？ - Rodrick Chapman

你为什么不使用符号函数？！？ - comonad

这张图片非常好。由于这两个数字是否定运算符x => -x的固定点，因此将0发送到0，将-2147483648发送到-2147483648。对于其余的数字，请按上面图片中的箭头进行操作。正如SurDin的答案及其评论所示，在这种情况下，将有两个数字，即2147483647和-2147483647，没有其他剩余的数字可以交换。 - Jeppe Stig Nielsen

它看起来像一个带有许多皱纹的笑脸。 - Anshul

Answer 9

问题没有说明函数 f 的输入类型和返回值应该是什么（至少你没有这样呈现）...

... 只是当n为32位整数时，f(f(n))=-n

那么，可以考虑类似这样的实现：

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

如果n是一个32位整数，那么语句 f(f(n)) == -n 将会成立。

显然，这种方法可以扩展到适用于更广泛的数字范围...

- Daniel LeCheminant

---

是的，我正在尝试类似的方法。不过你比我更快一步。+1 :) - jalf

非常聪明！这非常接近（并且有效地等同于）使用复数，这将是显而易见和理想的解决方案，但它被明确禁止。超出允许数字范围的工作。 - Kirk Broadhurst

Answer 10

对于JavaScript（或其他动态类型语言），您可以使函数接受 int 或对象，然后返回另一个。例如：

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

提供

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

或者在强类型语言中使用重载，尽管这可能会违反规则。

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

- cobbal

---

后者并不意味着需要“一个”（单数）函数的要求。 :) - Drew

删除答案的后半部分，这就是正确的答案。 - jmucchiello

定义一个数学函数以相同的方式进行操作也很容易，假设 f:ℚ→ℚ 被定义为 f(n) = n + 1/2，如果 n∈ℤ，则 -(n - 1/2) 如果 n∉ℤ。实际上是一样的，因为它们是不同的输入（当然，C语言中不同，因为它是两个不同的函数）。 - cobbal

在JavaScript中，函数是一个对象，因此可以保存状态。 - Nosredna

在我看来，函数 f(n){ return n.passed ? -n.val : {val:n, passed:1} } 更易读且更短。 - SamGoody