logo标签列表

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

mathinteger
849

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

设计一个函数f，使得：

f(f(n)) == -n

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

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

有什么想法吗？

6
这次面试是为了什么职位？ - tymtam
120个回答
16

我实际上并不是在试图给出问题本身的解决方案，但是我有一些评论。正如问题所述，这个问题是作为（工作？）面试的一部分提出的。

  • 我首先会问：“为什么需要这样的函数？这是什么更大的问题的一部分？”而不是立即尝试解决实际提出的问题。这展示了我的思维方式和我解决这类问题的方法。谁知道呢？这甚至可能是问题被问及面试的原因。如果答案是“不用管，假设它是必需的，并展示给我你如何设计这个函数。”那么我就会继续去做。
  • 然后，我会编写我将使用的C#测试用例代码（显而易见：循环从int.MinValue到int.MaxValue，并对该范围内的每个n调用f(f(n))，并检查结果是否为-n），告诉面试官我会使用测试驱动开发来得到这样的函数。
  • 只有在面试官继续要求我解决提出的问题时，我才会在面试本身中尝试草拟伪代码，以尝试得出某种答案。但是，如果面试官是公司的代表的话，我真的不认为我会急于接受这份工作...
哦，这个回答假设面试是针对C#编程相关职位的。如果面试是针对数学相关职位的话，当然会是一个愚蠢的回答。;-)
7
如果面试要求使用64位整数，你运行测试后面试就会立即结束，所以你很幸运他们只要求32位整数。;-) - alex2k8
事实上，如果我在面试中真的能够写出那个测试并运行它，那就太好了。;-) 我的观点是：我会尽量避免在面试中达到那个点。在我看来，编程更多地是一种“思维方式”，而不是“他如何编写代码行”。 - peSHIr
7
面试时不要遵循这个建议。面试官期望你真正回答问题。质疑问题的相关性除了可能会让面试官感到恼怒外，不会为你带来任何好处。设计一个琐碎的测试并不能使你更接近答案，而且你也无法在面试中运行它。如果你获得额外信息（例如32位），尝试想出它如何有用。 - Stefan Haustein
1
一个面试官如果在我询问更多信息时感到恼怒（同时可能质疑他的问题的相关性），那么这不是我想要一起工作的面试官。因此，在面试中，我会继续问这样的问题。如果他们不喜欢，我可能会结束面试，以避免进一步浪费我们双方的时间。我一点也不喜欢“我只是听从命令”的心态。你呢..？ - peSHIr
13

针对一个介于2^32 - 1之间的范围，使用C#进行操作。该范围内的所有数字均为int32类型，除了(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

输出：

2147483647
3
2
1
0
-1
-2
-3
-2147483647
这对于 f(0) 也不起作用，它等于 1073741824。f(1073741824) = 0。f(f(1073741824)) = 1073741824。 - Dinah
通常情况下，对于任何位数的二进制补码整数类型，该函数必须至少不能处理两个输入值。 - slacker
12

这个函数实际上需要将可用范围分成大小为4的周期，其中-n位于n的周期的对面。然而，0必须是大小为1的一个周期的一部分，否则 0->x->0->x != -x。由于0是孤独的，因此我们的范围（其大小为4的倍数）中必须有另外3个值不在适当的4元素周期内。

我选择这些额外的奇怪值为MIN_INT，MAX_INT和MIN_INT+1。此外，MIN_INT+1将正确映射到MAX_INT，但会停留在那里并且无法映射回来。我认为这是最好的折中方案，因为它具有良好的性质：只有极端值不能正常工作。此外，这意味着它将适用于所有 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)
12

没有人说它必须是无状态的。

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

这个方法有点作弊，但没有很多其他例子那么恶劣。更邪恶的方式是查看堆栈以查看调用者的地址是否为 &f，但这种方法会更具可移植性（尽管不是线程安全的... 线程安全的版本将使用 TLS）。更加邪恶：

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

当然，对于MIN_INT32的情况，这两个解决方案都不太可行，除非允许返回更宽的类型。

你可以在C语言中“升级”它以询问地址（是的，你必须通过引用作为指针获取它）例如： int f(int& n) { static int* addr = &n; if (addr == &n) { return -n; } return n; } - IUnknownPointer
11

我可以想象使用第31位作为虚数（i）位，这将是一种支持总范围一半的方法。

这会更加复杂，但并不比目前的最佳答案更有效。 - 1800 INFORMATION
1
@1800 信息：另一方面，定义域[-2^30+1, 2^30-1]是连续的，从数学角度来看更具吸引力。 - Jochen Walter
10

适用于 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
}
10

这个问题说明了“32位有符号整数”，但并没有指定它们是二进制补码还是一的补码。

如果使用一的补码，则所有2^32个值都以长度为四的周期出现 - 您不需要针对零使用特殊情况，也不需要条件语句。

在 C 语言中：

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

这个方法的工作原理如下：

  1. 交换高16位和低16位
  2. 反转其中一个块

经过两次操作后，我们得到了原值的按位取反。在补码表示中，这相当于取反。

示例：

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)
1
不同架构之间的字节顺序怎么处理？ - Steven
1
所有算术都是32位的。我不操作单独的字节，所以字节顺序不会影响它。 - finnw
这听起来非常接近。您可以假设输入为2补码。因此，您将转换为符号位表示。现在根据最后一位，您翻转第一位和最后一位或仅翻转最后一位。基本上，您仅否定偶数，并始终循环偶数/奇数。因此，在2次调用后，您从奇数返回到奇数，从偶数返回到偶数。最后，您将转换回2补码。已在下面某个地方发布了此代码。 - Stefan Haustein
9

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
5
如果你使用全局变量，可能会引起面试官对其不良影响的讨论，甚至可能导致你被淘汰。 - palswim
9
return x ^ ((x%2) ? 1 : -INT_MAX);
7
作为一名数学家，我想分享一下我的观点。我认为我有最有效的解决方案。
如果我没记错的话，你可以通过翻转第一个比特位来否定一个带符号的32位整数。例如，如果n=1001 1101 1110 1011 1110 0000 1110 1010，则-n=0001 1101 1110 1011 1110 0000 1110 1010。
那么我们如何定义一个函数f，它接受一个带符号的32位整数，并返回另一个带符号的32位整数，使得对f进行两次操作与翻转第一个比特位相同？
让我重新提出这个问题，而不提到像整数这样的算术概念。
我们如何定义一个函数f，它接受长度为32的零和一序列，并返回一个相同长度的零和一序列，使得对f进行两次操作与翻转第一个比特位相同？
观察：如果你能回答上述32位情况的问题，那么你也可以回答64位情况、100位情况等。你只需将f应用于前32位。
现在，如果你能回答2位情况的问题，万事大吉！
是的，结果表明更改前2位就足够了。
以下是伪代码：
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.

备注：步骤2和步骤3可以合并为(a,b) --> (-b, a)。听起来很熟悉吧？这应该会让你想起平面的90度旋转和乘以负1的平方根。

如果我只呈现伪代码而没有长篇大论的前奏，它看起来就像变出帽子里的兔子一样，我想解释一下我是如何得到解决方案的。

6
这是一个有趣的问题。你很懂数学。但这是一个计算机科学问题，所以你需要学习计算机。原码表示法是可以接受的，但它在大约60年前过时了。2的补码是最流行的。 - Windows programmer
5
这是你的函数两次作用后的结果：(a,b) --> (-b, a) --> (-a, -b)。但是我们想要得到的是(-a, b)，而不是(-a, -b)。 - buti-oxa
@buti-oxa，你说得对。两位操作应该是这样的：00 -> 01 -> 10 -> 11 -> 00。但是我的算法假设了现在不流行的符号-幅度表示法，正如Windows程序员所说，所以我认为我的算法没有什么用处。 - Yoo
那他不能做两次步骤吗？ - Nosredna
4
buti-oxa是完全正确的：该函数在两次调用后甚至不会翻转第一个位，它会翻转前两个位。翻转所有位更接近于2的补码所做的事情，但并不完全正确。 - redtuna
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接