设计函数f（f（n））==-n

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

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

有什么想法吗？

当前回答

根据微软/谷歌的面试官通常在面试中提出的问题，我认为提问者指的是一种创新、轻量级、简单的解决方案，它将使用按位操作，而不是那些复杂的高级答案。

灵感来自@eipipuz的回答，我编写了这个C++函数（但没有运行它）：

int32_t f(int32_t n){
    int32_t temp = n & 00111111111111111111111111111111;
    x = n >> 30;
    x++;
    x = x << 30;
    return x | temp;
}

它将n的最左边的两位存储在x中，将x加1，然后再次将其替换为n的最左侧的两位。

如果我们继续以另一个f（n）作为参数n运行f（n，则最左边的两个位将如下旋转：

00 --> 01 --> 10 --> 11 --> 00 ...

请注意，最右边的30位不变。8位整数示例：

示例1：

>f（00001111）=01001111>f（01001111）=10001111[这是原始值的负值，00001111]

示例2：

>f（11101010）=00101010>f（00101010）=01101010[这是原始值11101010的负值]

其他回答

这个问题并没有说明函数f的输入类型和返回值必须是什么（至少不是你给出的方式）。。。

…只是当n是32位整数时，f（f（n））=-n

那么，怎么样

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

如果n是32位整数，则语句f（f（n））==-n将为真。

显然，这种方法可以扩展到更大范围的数字。。。

我有另一个解决方案，它可以在一半时间内工作：

def f(x):
    if random.randrange(0, 2):
        return -x
    return x

怎么样

int f(int n)
{
    return -abs(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);

Python 2.6：

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)

我意识到这对讨论毫无帮助，但我无法抗拒。

推荐文章