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

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

有什么想法吗?


当前回答

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

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

  return $answer;
}

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

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

其他回答

你没说他们期望什么样的语言。。。这是一个静态解决方案(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()

将n转换为符号和幅度表示;添加范围的1/4;转换回。


    #define STYPE int
    STYPE sign_bit = (unsigned STYPE) 1 << ( sizeof ( STYPE ) * 8  - 1 );
    STYPE f ( STYPE f )
    {
        unsigned STYPE smf = f > 0 ? f : -f | sign_bit;
        smf += sign_bit >> 1;
        return smf & sign_bit ? -( smf & ~sign_bit ) : smf;
    }

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

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

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

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

我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:

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

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

另一个作弊解决方案。我们使用允许运算符重载的语言。然后我们让f(x)返回重载==的值,以始终返回true。这似乎与问题描述相符,但显然违背了谜题的精神。

Ruby示例:

class Cheat
  def ==(n)
     true
  end
end

def f(n)
  Cheat.new
end

这给了我们:

>> f(f(1)) == -1
=> true

而且(不太令人惊讶)

>> f(f(1)) == "hello world"
=> true

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

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

  return $answer;
}

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

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