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

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

有什么想法吗?


当前回答

将n转换为符号和幅度表示;添加范围的1/4;转换回。


    #define STYPE int
    STYPE sign_bit = (unsigned STYPE) 1 << ( sizeof ( STYPE ) * 8  - 1 );
    STYPE f ( STYPE f )
    {
        unsigned STYPE smf = f > 0 ? f : -f | sign_bit;
        smf += sign_bit >> 1;
        return smf & sign_bit ? -( smf & ~sign_bit ) : smf;
    }

其他回答

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

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

这个怎么样?

int nasty(int input)
{
    return input + INT_MAX/2;
}

另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29

整数ffn(整数n){

    n = n ^ (1 << 30); //flip the bit
    if (n>0)// if negative then there's a two's complement
    {
        if (n & (1<<30))
        {
            return n;
        }
        else
        {
            return -n;
        }
    }
    else
    {
        if (n & (1<<30))
        {
            return -n;
        }
        else
        {
            return n;
        }
    }


}

C++解决方案;

long long f(int n){return static_cast <long long> (n);}
int f(long long n){return -static_cast <int> (n);}

int n = 777;
assert(f(f(n)) == -n);