我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

使用问题中给出的信息,您可以

从2-完成转换为符号位表示如果设置了最后一位,则翻转符号位和最后一位;否则,只翻转最后一位转换回2-完成。

所以你基本上是奇数->偶数->奇数或偶数->奇数->偶数,只对偶数更改符号。唯一不适用的数字是-2^31

代码:

function f(x) {
  var neg = x < 0;
  x = Math.abs(x) ^ 1;
  if (x & 1) {
    neg = !neg;
  }
  return neg ? -x : x;
}

其他回答

容易的:

function f($n) {
   if ($n%2 == 0) return ($n+1)*-1;
   else return ($n-1);
}
void f(int x)
{
     Console.WriteLine(string.Format("f(f({0})) == -{0}",x));
}

抱歉,伙计们。。。这太诱人了;)

我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。

作为一名数学家,我想分享我对这个有趣问题的看法。我认为我有最有效的解决方案。

如果我没记错的话,只需翻转第一位,就可以将有符号的32位整数取反。例如,如果n=1001 1101 1110 1011 1110 0000 1110 1010,则-n=0001 1101 11101 1011 11100 0000 1110 010。

那么,我们如何定义一个函数f,它接受一个带符号的32位整数,并返回另一个有符号的32位数整数,该函数的属性是:接受两次f与翻转第一位相同?

让我重新表述这个问题,而不提整数之类的算术概念。

我们如何定义一个函数f,它接受长度为32的一系列0和1,并返回长度相同的一系列零和1,同时具有两次接受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的平方根。

如果我只是单独展示了伪代码,而没有冗长的前奏,那么它看起来就像脱口而出的兔子,我想解释一下我是如何得到解决方案的。

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}