我在上次面试中遇到的一个问题是:

设计函数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%。

其他回答

下面是一个简短的Python答案:

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

一般情况

稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

或者,为了更容易理解,这里是k=3的示例循环:

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。

兼容范围分析

映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。

对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。

嗯,我既不是数学,也不是编程高手,但这不是很容易吗?

int f(int i) {
    static bool b;
    if (b) {
        b = !b;
        return i;
    } else {
        b = !b;
        return -i;
    }
}

用大小正值和负值INT_MIN、INT_MAX进行测试,似乎可以。。。如果这是一个问题,可以使线程安全,但这不是任务的一部分。

或者我错过了什么?

C函数:

int f(int n) /* Treats numbers in the range 0XC0000000 to 0X3FFFFFFF as valid to
                generate f(f(x)) equal to -x. If n is within this range, it will
                project n outside the range. If n is outside the range, it will
                return the opposite of the number whose image is n. */
{
    return n ? n > 0 ? n <= 0X3FFFFFFF ? 0X3FFFFFFF + n : 0X3FFFFFFF - n :\
           n >= 0XC0000000 ? 0XC0000000 + n : 0XC0000000 - n : 0;
}

Ideone测试和下载链接

我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。

怎么样:

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


为了使其适用于实数,您需要替换(-1)中的nⁿ 如果n>0,则为{上限(n);如果n<0},则为下限(n)。

在C#中(适用于任何双精度,溢出情况除外):

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));
}