设计函数 f（f（n））== - n

我上次采访时遇到的一个问题：

设计一个函数f ，这样：
f(f(n)) == -n
其中n是 32 位有符号整数 ; 你不能使用复数运算。
如果您无法为整个数字范围设计此类功能，请将其设计为可能的最大范围。

有任何想法吗？

math integer

你没有说他们期望的那种语言...... 这是一个静态的解决方案（Haskell）。它基本上搞乱了 2 个最重要的位：

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

在 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 自动将整数提升为任意长度的长度。在其他语言中，最大的正整数将溢出，因此它将适用于除了那个之外的所有整数。

为了使它适用于实数，你需要将{ ceiling(n) if n>0; floor(n) if n<0 } in（-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.）

此外，对于任何x和y ，假设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 个号码作为奖励。（但这只是一个愚蠢的。）

协慌网

设计函数 f（f（n））== - n

答案