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

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

有什么想法吗?


当前回答

简单的Python解决方案之所以成为可能,是因为对f(x)应该输出的内容没有限制,只有f(f(x)):

def f(x):
    return (isinstance(x, tuple) and -x[0]) or (x,)

其他回答

这里有一个证明,如果不使用额外信息(除了32位的int),那么对于所有数字,这样的函数都不可能存在:

我们必须使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之外的所有整数分成4个集合,但我们有奇数个这样的整数;不仅如此,如果我们去掉没有正对应的整数,我们仍然有2(mod4)个数。

如果我们去掉剩下的2个最大数(通过abs值),我们可以得到函数:

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,并获得我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)

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

如果我没记错的话,只需翻转第一位,就可以将有符号的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的平方根。

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

另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让f(x)返回重载==的值,以始终返回true。这似乎与问题描述相符,但显然违背了谜题的精神。

Ruby示例:

class Cheat
  def ==(n)
     true
  end
end

def f(n)
  Cheat.new
end

这给了我们:

>> f(f(1)) == -1
=> true

而且(不太令人惊讶)

>> f(f(1)) == "hello world"
=> true
int f(int x){
    if (x < 0)
        return x;
    return ~x+1; //two's complement
}

一个C++版本,可能会稍微改变规则,但适用于所有数值类型(浮点、整型、双精度),甚至是重载一元负号的类类型:

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