我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
好问题!
这花了我大约35秒的时间思考并写下:
int f(int n){
static int originalN=0;
if (n!=0)
originalN=n;
return n-originalN;
}
其他回答
这是一个C/C++解决方案,它不使用任何按位运算符,也不需要任何数学库,尽管这有点作弊。。。
double f(double n)
{
if (n == (double)(int)n)
return n + 0.5;
else
return -(n - 0.5);
}
这适用于所有32位整数,只有一个异常0x80000000(因为它的相反值不能存储在32位整数系统中)。f(f(n))==-n将始终为真,除非在这种情况下。
不过,我相信有一种更简单、更快的方法来实现它。这只是我第一个想到的。
这个问题并没有说明函数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将为真。
显然,这种方法可以扩展到更大范围的数字。。。
这将在非常广泛的数字范围内发挥作用:
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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为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;
}
}
}
这很简单!
每个数字以4为周期映射到另一个数字,其中所需条件成立。
例子:
规则如下:
0→ 0±2³¹ → ±2³¹古怪的→ 甚至,甚至→ -奇数:对于所有k,0<k<2³⁰: (2k-1)→ (2k)→ (-2k+1)→ (-2k)→ (2k-1)
唯一不匹配的值是±(2³¹-1),因为只有两个。必须有两个不能匹配,因为在二进制补码系统中只有四个数字的倍数,其中0和±2³¹已被保留。
在一的补码系统中,存在+0和-0。我们开始了:
对于所有k,0<k<2³⁰: (+2k)→ (+2k+1)→ (-2k)→ (-2k-1)→ (+2k)