我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这适用于1073741823至1073741822范围:
int F(int n)
{
if(n < 0)
{
if(n > -1073741824)
n = -1073741824 + n;
else n = -(n + 1073741824);
}
else
{
if(n < 1073741823)
n = 1073741823 + n;
else n = -(n - 1073741823);
}
return n;
}
它的工作原理是获取32位有符号整数的可用范围并将其一分为二。函数的第一次迭代将n自身置于该范围之外。第二次迭代检查它是否在该范围之外-如果是,则将其放回该范围内,但使其为负值。
这实际上是一种保留关于值n的额外“位”信息的方法。
其他回答
int f(int x){
if (x < 0)
return x;
return ~x+1; //two's complement
}
这个问题并没有说明函数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将为真。
显然,这种方法可以扩展到更大范围的数字。。。
int j = 0;
void int f(int n)
{
j++;
if(j==2)
{
j = 0;
return -n;
}
return n;
}
:D
适用于n=[0..2^31-1]
int f(int n) {
if (n & (1 << 31)) // highest bit set?
return -(n & ~(1 << 31)); // return negative of original n
else
return n | (1 << 31); // return n with highest bit set
}
Clojure解决方案:
(defmacro f [n] (if (list? n) `(- ~n) n))
也适用于任何大小的正整数和负整数、双整数和比率!