我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这将在非常广泛的数字范围内发挥作用:
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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
其他回答
我试着打高尔夫,这是罗德里克·查普曼的回答。
无分支:74个字符
int f(int i){return(-((i&1)<<1)|1)*i-(-((i>>>31)<<1)|1)*(((i|-i)>>31)&1);}
带有分支,Java风格:58个字符
int f(int i){return i==0?0:(((i&1)==0?i:-i)+(i>0?-1:1));}
带分支,C样式:52个字符
int f(int i){return i?(((i&1)?-i:i)+(i>0?-1:1)):0;}
经过快速但有效的基准测试后,分支版本在我的机器上的速度提高了33%。(正数和负数的随机数据集,足够的重复,并防止编译器在预热时优化代码。)考虑到非分支版本中的操作数量以及可能的良好分支预测,这并不奇怪,因为函数被调用了两次:f(f(i))。当我将基准更改为度量:f(I)时,分支版本只快28%。我认为这证明了分支预测在第一种情况下确实有一些好处。更多证明:当使用f(f(f)(f(i)))进行测试时,分支版本的速度会快42%。
以下情况如何:
int f (int n)
{
static bool pass = false;
pass = !pass;
return pass? n : -n;
}
你没说他们期望什么样的语言。。。这是一个静态解决方案(Haskell)。这基本上是在搞乱两个最重要的比特:
f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
| otherwise = complementBit x 30
在动态语言(Python)中要容易得多。只需检查参数是否为数字X,并返回返回-X的lambda:
def f(x):
if isinstance(x,int):
return (lambda: -x)
else:
return x()
使用全局。。。但事实如此?
bool done = false
f(int n)
{
int out = n;
if(!done)
{
out = n * -1;
done = true;
}
return out;
}
很简单,只需让f返回看起来等于任何整数的值,并且可以从整数转换。
public class Agreeable
{
public static bool operator==(Agreeable c, int n)
{ return true; }
public static bool operator!=(Agreeable c, int n)
{ return false; }
public static implicit operator Agreeable(int n)
{ return new Agreeable(); }
}
class Program
{
public static Agreeable f(Agreeable c)
{ return c; }
static void Main(string[] args)
{
Debug.Assert(f(f(0)) == 0);
Debug.Assert(f(f(5)) == -5);
Debug.Assert(f(f(-5)) == 5);
Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
}
}