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

设计函数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的负值]

其他回答

本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则0->x->0->x!=-x.因为0是单独的,所以在我们的范围内必须有3个其他值(其大小是4的倍数)不在具有4个元素的正确循环中。

我选择这些额外的奇怪值为MIN_INT、MAX_INT和MIN_INT+1。此外,MIN_INT+1将正确映射到MAX_INT,但会被卡在那里而不能映射回来。我认为这是最好的妥协,因为它有一个很好的特性,即只有极端值不能正常工作。此外,这意味着它将适用于所有BigInt。

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

这个怎么样?

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

我想我会先不看别人的答案就试试这个:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int f(int n) {
    if(n > 0) {  
        if(n % 2)
            return -(++n);
        else {
            return (--n);

        }
    }
    else {
        if(n % 2)
            return -(--n);
        else {
            return (++n);

        }
    }
}

int main(int argc, char* argv[]) {
    int n;
    for(n = INT_MIN; n < INT_MAX; n++) {
        int N = f(f(n));

        if(N != -n) {
            fprintf(stderr, "FAIL! %i != %i\n", N, -n);
        }
    }
    n = INT_MAX;
    int N = f(f(n));
    if(N != -n) {
        fprintf(stderr, "FAIL! n = %i\n", n);
    }
    return 0;
}

输出:[无]

嗯,我既不是数学,也不是编程高手,但这不是很容易吗?

int f(int i) {
    static bool b;
    if (b) {
        b = !b;
        return i;
    } else {
        b = !b;
        return -i;
    }
}

用大小正值和负值INT_MIN、INT_MAX进行测试,似乎可以。。。如果这是一个问题,可以使线程安全,但这不是任务的一部分。

或者我错过了什么?

我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成4个数的小集合:

 1  → 2    3  → 4    5  → 6
 ↑    ↓    ↑    ↓    ↑    ↓   ...
-2 ← -1   -4 ← -3   -6 ← -5

这很容易翻译成代码。注意,偶数改变符号,奇数增加或减少1。在C#中,它看起来像这样:

public static int f(int x)
{
    if(x == 0)
        return 0;

    if(x > 0)
        return (x % 2 == 0) ? -x+1 : x+1;

    // we know x is negative at this point
    return (x % 2 == 0) ? -x-1 : x-1;
}

当然,您可以通过使用巧妙的技巧来缩短此方法,但我认为这段代码最好地解释了它本身。

然后是范围。32位整数的范围从-2^31到2^31-1。数字2^31-1、-2^31-1和-2^31超出了f(x)的范围,因为缺少数字2^31。