我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
我试着打高尔夫,这是罗德里克·查普曼的回答。
无分支: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%。
其他回答
这个Perl解决方案适用于整数、浮点数和字符串。
sub f {
my $n = shift;
return ref($n) ? -$$n : \$n;
}
尝试一些测试数据。
print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';
输出:
-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
这将在非常广泛的数字范围内发挥作用:
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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
根据您的平台,某些语言允许您在函数中保持状态。VB.Net,例如:
Function f(ByVal n As Integer) As Integer
Static flag As Integer = -1
flag *= -1
Return n * flag
End Function
IIRC、C++也允许这样做。我怀疑他们正在寻找不同的解决方案。
另一个想法是,由于它们没有定义函数第一次调用的结果,因此可以使用奇数/均匀度来控制是否反转符号:
int f(int n)
{
int sign = n>=0?1:-1;
if (abs(n)%2 == 0)
return ((abs(n)+1)*sign * -1;
else
return (abs(n)-1)*sign;
}
所有偶数的幅度加一,所有奇数的幅度减一。两次调用的结果大小相同,但在一次调用中,我们甚至交换了符号。在某些情况下,这不会起作用(-1,max或min int),但它的效果比迄今为止任何其他建议都要好得多。
这对所有负数都是正确的。
f(n) = abs(n)
因为两个互补整数的负数比正数多一个,所以f(n)=abs(n)比f(n(n)=n>0-n:n溶液,与f(n)=-abs(n)相同。一个接一个…:D
更新
不,这对一个以上的案例无效,因为我刚从李布的评论中认识到。。。abs(Int.Min)将溢出。。。
我也想过使用mod 2信息,但得出的结论是,它不起作用。。。到早期。如果操作正确,它将适用于除Int.Min之外的所有数字,因为这将溢出。
更新
我玩了一段时间,寻找一个很好的位操作技巧,但我找不到一个很不错的单行线,而mod 2解决方案适合一个。
f(n) = 2n(abs(n) % 2) - n + sgn(n)
在C#中,这变成了以下内容:
public static Int32 f(Int32 n)
{
return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}
要使其适用于所有值,必须将Math.Abs()替换为(n>0)+n:-n,并将计算包含在未选中的块中。然后,您甚至可以像未检查的否定一样将Int.Min映射到自身。
更新
受另一个答案的启发,我将解释函数是如何工作的,以及如何构造这样的函数。
让我们从头开始。函数f被重复应用于给定值n,产生一系列值。
n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...
这个问题要求f(f(n))=-n,即f的两个连续应用否定这个论点。另外两次应用f-总共四次-再次否定论点,再次产生n。
n => f(n) => -n => f(f(f(n))) => n => f(n) => ...
现在有一个明显的长度为4的循环。代入x=f(n),并注意所获得的方程式f(f(f)n))=f(f f(x))=-x成立,得出以下结果。
n => x => -n => -x => n => ...
所以我们得到一个长度为4的循环,有两个数字,两个数字被取反。如果将循环想象为矩形,则取反的值位于相反的角落。
构建这样一个循环的许多解决方案之一是从n开始的以下方法。
n => negate and subtract one -n - 1 = -(n + 1) => add one -n => negate and add one n + 1 => subtract one n
一个具体的例子是这样一个循环:+1=>-2=>-1=>+2=>+1。我们快完成了。注意到所构造的循环包含一个奇数正数,它的偶数后继数,并且两个数都是负数,我们可以很容易地将整数划分为许多这样的循环(2^32是四的倍数),并找到了满足条件的函数。
但我们有一个零的问题。循环必须包含0=>x=>0,因为零对自身求反。因为循环状态已经是0=>x,所以它遵循0=>x=>0=>x。这只是一个长度为2的循环,x在两次应用后变为自身,而不是变为-x。幸运的是,有一个案例解决了这个问题。如果X等于零,我们得到一个长度为1的循环,它只包含零,我们解决了这个问题,得出结论,零是f的不动点。
完成?几乎我们有2^32个数字,零是留下2^32-1个数字的固定点,我们必须将这个数字分成四个数字的循环。糟糕的是,2^32-1不是四的倍数-在任何长度为四的循环中都会保留三个数字。
我将使用范围从-4到+3的较小的3位带符号iteger集来解释解决方案的其余部分。我们用零结束了。我们有一个完整的循环+1=>-2=>-1=>+2=>+1。现在让我们构建从+3开始的循环。
+3 => -4 => -3 => +4 => +3
出现的问题是+4不能表示为3位整数。我们可以通过将-3减为+3来获得+4,这仍然是一个有效的3位整数,但然后将1加上+3(二进制011)得到100个二进制。它被解释为无符号整数,它是+4,但我们必须将它解释为有符号整数-4。因此实际上,本例中的-4或一般情况下的Int.MinValue是整数算术否定的第二个不动点-0和Int.MinValue映射到它们自己。所以循环实际上如下。
+3 => -4 => -3 => -4 => -3
这是一个长度为2的循环,另外+3通过-4进入循环。因此,-4在两个函数应用程序之后正确映射到自身,+3在两个功能应用程序之后被正确映射到-3,但-3在两个应用程序之后错误映射到自身。
所以我们构造了一个函数,它适用于除1以外的所有整数。我们能做得更好吗?不,我们不能。为什么?我们必须构造长度为4的循环,并且能够覆盖多达四个值的整个整数范围。剩下的值是必须映射到自身的两个固定点0和Int.MinValue,以及必须由两个函数应用程序相互映射的两个任意整数x和-x。
为了将x映射到-x,反之亦然,它们必须形成一个四循环,并且必须位于该循环的相对角。因此,0和Int.MinValue也必须位于相反的角落。这将正确映射x和-x,但在两个函数应用程序之后交换两个固定点0和Int.MinValue,并留下两个失败的输入。因此,不可能构造一个适用于所有值的函数,但我们有一个适用所有值(除了一个值)的函数,这是我们所能达到的最佳效果。
创建许多解的一种方法是注意,如果我们将整数划分为两个集合S和R
那么我们可以如下创建f:
如果x在R中,则f(x)=g(x)
如果x在S中,则f(x)=-invg(x)
其中invg(g(x))=x,所以invg是g的逆函数。
上面提到的第一个解决方案是分区R=偶数,R=奇数,g(x)=x+1。
我们可以取任意两个无限集合T,P s.T T+U=整数集合,取s=T+(-T),R=U+(-U)。
然后-S=S和-R=R通过它们的定义,我们可以将g取为从S到R的任何1-1对应关系,这必须存在,因为这两个集合都是无限的和可数的。
因此,这将为我们提供许多解决方案,但并非所有解决方案都可以编程,因为它们不会被有限地定义。
例如:
R=可被3整除的数字,S=不可被3除的数字。
然后我们取g(6r)=3r+1,g(6r+3)=3r+2。