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

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

有什么想法吗?


当前回答

记住你的上一个状态不是一个足够好的答案吗?

int f (int n)
{
    //if count 
    static int count = 0;

    if (count == 0)
        { 
            count = 1;
            return n;
        }

    if (n == 0)
        return 0;
    else if (n > 0)
    {
        count = 0;
        return abs(n)*(-1);
    } 
    else
    {
        count = 0;
        return abs(n);
    }
}

int main()
{
    int n = 42;
    std::cout << f(f(n))
}

其他回答

有些类似,但我只是想写下我的第一个想法(用C++)

#include <vector>

vector<int>* f(int n)
{
  returnVector = new vector<int>();
  returnVector->push_back(n);
  return returnVector;
}

int f(vector<int>* n) { return -(n->at(0)); }

仅使用重载使f(f(n))实际调用两个不同的函数

很简单,只需让f返回看起来等于任何整数的值,并且可以从整数转换。

public class Agreeable
{
    public static bool operator==(Agreeable c, int n)
        { return true; }

    public static bool operator!=(Agreeable c, int n)
        { return false; }

    public static implicit operator Agreeable(int n)
        { return new Agreeable(); }
}

class Program
{
    public static Agreeable f(Agreeable c)
        { return c; }

    static void Main(string[] args)
    {
        Debug.Assert(f(f(0)) == 0);
        Debug.Assert(f(f(5)) == -5);
        Debug.Assert(f(f(-5)) == 5);
        Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
    }
}

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

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

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

我认为最大的可能范围是暗示模块化算术解决方案。在一些模基M中,有一个数,当平方等于M-1(等于-1)。例如,如果M=13,5*5=25,25 mod 13=12(=-1)总之,这里有一些M=2**32-3的python代码。

def f(x):
    m=2**32-3;
    halfm=m//2;
    i_mod_m=1849436465
    if abs( x ) >halfm:
        raise "too big"
    if x<0:
        x+=m
    x=(i_mod_m*x) % m
    if (x>halfm):
        x-=m
    return x;

注意,有3个值不适用于2**31-1、-(2**31-1)和-(2*#31)

const unsigned long Magic = 0x8000000;

unsigned long f(unsigned long n)
{    
    if(n > Magic )
    {
        return Magic - n;
    }

    return n + Magic;
} 

0~2^31