设计函数 f(f(n))== -n

我上次面试时遇到的一个问题:

设计一个函数f ,使得:

f(f(n)) == -n

其中n是一个 32 位有符号整数 ; 您不能使用复数算法。

如果您不能为整个数字范围设计这样的函数,请为最大范围设计它。

有任何想法吗?

答案

您没有说他们期望使用哪种语言... 这是一个静态解决方案(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()

怎么样:

f(n) = sign(n) - (-1) n * n

在 Python 中:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python 自动将整数提升为任意长度的 long。在其他语言中,最大的正整数将溢出,因此它将适用于除那个整数以外的所有整数。


为了使它适用于实数,您需要将{ ceiling(n) if n>0; floor(n) if n<0 } -1) n 中n替换为{ ceiling(n) if n>0; floor(n) if n<0 }

在 C#中(除了在溢出情况下,任何 double 都适用):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

这证明了为什么这样的函数如果不使用额外的信息(32 位的 int 除外),对于所有数字都不存在:

我们必须使 f(0)=0。(证明:假设 f(0)= x。然后 f(x)= f(f(0))= -0 =0。现在,-x = f(f(x ))= f(0)= x,这意味着 x =0。)

此外,对于任何xy ,假设f(x) = y 。那么我们想要f(y) = -x 。并且f(f(y)) = -y => f(-x) = -y 。总结一下:如果f(x) = y ,则f(-x) = -y ,并且f(y) = -x ,并且f(-y) = x

因此,我们需要将除 0 以外的所有整数划分为 4 组,但是此类整数的数量为奇数;不仅如此,如果我们删除没有正对数的整数,我们仍然有 2(mod4)个数字。

如果我们删除剩下的 2 个最大数(按 abs 值),则可以获得函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}

当然,另一种选择是不遵守 0,并获得我们删除的 2 个数字作为奖励。 (但是,那真是愚蠢。)

感谢 C ++ 中的重载:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

或者,您可以滥用预处理器:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

所有负数都是这样。

f(n) = abs(n)

因为对于二进制补码整数,负数要多于正数,所以f(n) = abs(n)f(n) = n > 0 ? -n : nf(n) = -abs(n)相同的f(n) = n > 0 ? -n : n解。让你一个...:D

更新

不,它在一种情况下是无效的,因为我刚刚被 litb 的评论所认识... abs(Int.Min)只会溢出...

我也考虑过使用 mod 2 信息,但得出的结论是,它直到早期都行不通。如果操作正确,它将对除Int.Min以外的所有数字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并将计算包括在unchecked块中。然后,您甚至可以将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(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 的倍数 - 在任何长度为 4 的循环中都将保留 3 个数字。

我将使用从-4+3的较小的 3 位带符号的 Iteger 集来解释解决方案的其余部分。我们完成了零。我们有一个完整的周期+1 => -2 => -1 => +2 => +1 。现在让我们构造一个从+3开始的循环。

+3 => -4 => -3 => +4 => +3

出现的问题是+4不能表示为 3 位整数。我们可以通过将-3减为+3 (仍然是有效的 3 位整数)来获得+4 ,但是将+3加一个(二进制011 )则得到100二进制。解释为无符号整数,它是+4但我们必须将其解释为有符号整数-4 。因此,对于该示例Int.MinValue ,实际上-4或通常情况下的Int.MinValue是整数算术Int.MinValue反的第二个固定点0Int.MinValue各自映射到它们。因此,周期实际上如下。

+3 =>    -4 => -3 => -4 => -3

这是一个长度为 2 的循环,另外+3通过-4进入循环。结果,在两个函数应用程序之后-4正确地映射到其自身,在两个函数应用程序之后+3正确地映射到-3 ,但是在两个函数应用程序之后-3被错误地映射到自身。

因此,我们构造了一个函数,该函数可用于除一个整数之外的所有整数。我们可以做得更好吗?不,我们不可以。为什么?我们必须构造长度为 4 的循环,并且能够覆盖整个整数范围(最多四个值)。其余值是必须映射到自身的两个固定点0Int.MinValue ,以及必须通过两个函数应用程序相互映射的两个任意整数x-x

要将x映射到-x ,反之亦然,它们必须形成四个周期,并且必须位于该周期的相对角。因此, 0Int.MinValue也必须位于相反的角。这将正确地映射x-x但在两个函数应用程序之后交换两个固定点0Int.MinValue ,并给我们留下两个失败的输入。因此,不可能构造一个适用于所有值的函数,但是我们拥有一个适用于除一个值之外的所有值的函数,这是我们可以实现的最佳结果。

使用复数,可以有效地将数字取负的任务分为两个步骤:

  • 将 n 乘以 i,得到 n * i,即 n 逆时针旋转 90°
  • 再乘以 i,得到 - n

很棒的是,您不需要任何特殊的处理代码。乘以我就可以了。

但是您不允许使用复数。因此,您必须使用部分数据范围以某种方式创建自己的虚轴。由于您需要的假想(中间)值与初始值一样多,因此只剩下一半的数据范围。

我假设下一个带符号的 8 位数据,试图在下图上形象化。您必须将其缩放为 32 位整数。初始 n 的允许范围是 - 64 至 + 63。这是该函数对正数 n 的作用:

  • 如果 n 在 0..63(初始范围)内,则函数调用加 64,将 n 映射到范围 64..127(中间范围)
  • 如果 n 在 64..127(中间范围)中,则该函数从 64 中减去 n,将 n 映射到范围 0 ..- 63

对于负数 n,该函数使用中间范围 - 65 ..- 128。

替代文字

除 int.MaxValue 和 int.MinValue 以外的作品

public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

画报

问题没有说明函数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为真。

显然,这种方法可以扩展以适用于更大范围的数字...

对于 javascript(或其他动态类型的语言),您可以让函数接受一个 int 或一个对象,然后返回另一个。即

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

给予

js> f(f(10))  
-10
js> f(f(-10))
10

或者,您可以在强类型语言中使用重载,尽管这可能会违反规则,即

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}