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

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

有什么想法吗?


当前回答

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

我想我会在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(); }

其他回答

或者,您可以滥用预处理器:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

另一种利用短路的Javascript解决方案。

​function f(n) {return n.inv || {inv:-n}}

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

类似于python中的函数重载解决方案:

def f(number):
 if type(number) != type([]):
  return [].append(number)
 else:
  return -1*number[0]

备选方案:静态数据成员

我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自viraptor先前使用lambda的Python答案。读者可能认为该解决方案仅在非类型化语言中可行,而在类型化语言中将需要一些明确的额外标记。

但下面是Haskell中的解决方案1(我不是Haskell专家)。它有点作弊,因为从技术上讲,两个f是两个不同的实现。(一个f::Int->()->Int,另一个f::(()->Int)->Int)

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

module Main where

class Tran σ τ | σ -> τ where
  tran :: σ -> τ

instance Tran Int (() -> Int) where
  tran n = \_ -> (-n)

instance Tran (() -> Int) Int where
  tran g = g ()

f :: Tran σ τ => σ -> τ
f = tran

main :: IO ()
main = do
  print $ f (f (42 :: Int)) -- --> -42
  print $ f (f (0 :: Int)) -- --> 0
  print $ f (f (-69 :: Int)) -- --> 69

接下来是Typed Racket中的解决方案2。这一个满足了最大可能域的属性,因为Racket中的Number最多包含复数:

#lang typed/racket

(: f (case->
      [Number -> (-> Number)]
      [(-> Number) -> Number]))
(define (f x)
  (if (number? x) (λ () (- x)) (x)))

(f (f 42))    ; --> -42
(f (f 0))     ; --> 0
(f (f -69))   ; --> 69
(f (f 3/4))   ; --> -3/4
(f (f 8+7i))  ; --> -8-7i
int func(int a)  
{   
    static int p = 0;  
    int ret = a;  

    if ( p ) ret *= -1;  
    p ^= 1;  

    return ret;  
}