我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这个想法已经在其他答案中使用过,但我把它融入了Python的一行:
def f(n):
return str(n) if type(n) == int else -int(n)
其他回答
C#表示2^32-1个数字的范围,所有整数32(int32.MinValue除外)
Func<int, int> f = n =>
n < 0
? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
: (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));
Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
for (int i = -3; i <= 3 ; i++)
Console.WriteLine(f(f(i)));
Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647
打印:
2147483647
3
2
1
0
-1
-2
-3
-2147483647
根据微软/谷歌的面试官通常在面试中提出的问题,我认为提问者指的是一种创新、轻量级、简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。
灵感来自@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的负值]
这将在非常广泛的数字范围内发挥作用:
static int f(int n)
{
int lastBit = int.MaxValue;
lastBit++;
int secondLastBit = lastBit >> 1;
int tuple = lastBit | secondLastBit;
if ((n & tuple) == tuple)
return n + lastBit;
if ((n & tuple) == 0)
return n + lastBit;
return -(n + lastBit);
}
我最初的方法是使用最后一位作为检查位,以了解我们在第一次或第二次调用中的位置。基本上,我会在第一次调用后将此位设置为1,以向第二次调用发出第一次调用已经通过的信号。但是,这种方法被负数所击败,负数的最后一位在第一次调用期间已经到达1。
同样的理论适用于大多数负数的倒数第二位。但是,通常发生的情况是,大多数情况下,最后一位和第二位是相同的。它们要么都是负数的1,要么都是正数的0。
所以我的最后一个方法是检查它们是否都是1或都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
我有另一个解决方案,它可以在一半时间内工作:
def f(x):
if random.randrange(0, 2):
return -x
return x
int func(int a)
{
static int p = 0;
int ret = a;
if ( p ) ret *= -1;
p ^= 1;
return ret;
}