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

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

有什么想法吗?


当前回答

该问题表示“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)

其他回答

这也是一个解决方案(但我们稍微改变了一下规则):

def f(n):
    if isinstance(n,int):
        return str(n)
    else:
        return -int(n)

我还没有看其他答案,我假设已经彻底讨论了按位技术。

我想我会在C++中想出一些邪恶的东西,希望不会上当受骗:

struct ImplicitlyConvertibleToInt
{
    operator int () const { return 0; }
};

int f(const ImplicitlyConvertibleToInt &) { return 0; }

ImplicitlyConvertibleToInt f(int & n)
{
    n = 0; // The problem specification didn't say n was const
    return ImplicitlyConvertibleToInt();
}

整个ImplicitlyConvertableToInt类型和重载是必需的,因为临时变量不能绑定到非常量引用。

当然,现在来看它,f(n)是否在-n之前执行是不确定的。

对于这种程度的邪恶,也许一个更好的解决方案是:

struct ComparesTrueToInt
{
    ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }

ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }
f(n) { return IsWholeNumber(n)? 1/n : -1/n }

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

适用于整数、浮点数和数字字符串!

只是意识到这会做一些不必要的工作,但是,不管怎样

没有人说它必须是无国籍的。

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

作弊,但不如很多例子。更糟糕的是,查看堆栈以查看调用者的地址是否为-f,但这将更具可移植性(虽然不是线程安全的……线程安全版本将使用TLS)。更邪恶的是:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

当然,对于MIN_INT32的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。