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

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

Python 2.6:

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)

我意识到这对讨论毫无帮助,但我无法抗拒。

其他回答

对于所有32位值(注意,-0是-2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

基本上需要将每个-x=>x=>-x循环与y=>-y=>y循环配对。所以我把裂口的两边配对。

例如,对于4位整数:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3

这是rossfabricant答案的C实现。注意,由于我始终使用32位整数,f(f(2147483647))==2147483648,而不是-2147483647。

int32_t f( int32_t n )
{
    if( n == 0 ) return 0;
    switch( n & 0x80000001 ) {
        case 0x00000000:
            return -1 * ( n - 1 );
        case 0x00000001:
            return n + 1;
        case 0x80000000:
            return -1 * ( n + 1 );
        default:
            return n - 1;
    }
}

如果您将问题定义为允许f()接受并返回int64_t,则会涉及2147483647。当然,switch语句中使用的文字必须更改。

我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。

int f(int n)
{
    static bool eFlag = false; // Only executed once
    eFlag = !eFlag;
    return eFlag?-n:n;
}
int f(int n) {
    return ((n>0)? -1 : 1) * abs(n);
}

该问题表示“32位有符号整数”,但没有指定它们是2个补码还是1个补码。

如果使用1补码,则所有2^32值都出现在长度为4的循环中-不需要零的特殊情况,也不需要条件。

在C中:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

这项工作由

交换高位和低位16位块反转其中一个块

两次传递后,我们得到原始值的位逆。在一中补语表示等同于否定。

示例:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)