两个压缩有符号整数相乘

Question

Stockfish 国际象棋引擎需要存储残局得分和中局得分以进行评估。

它将它们打包成一个 ，而不是单独存储它们int。中局得分存储在低 16 位中。如果中局得分为正，则残局得分存储在高 16 位中；如果中局得分为负，则减一。

这样做的优点是可以并行地对两个数字进行运算（加法、减法、求反和乘法）。

这是代码：

/// Score enum stores a middlegame and an endgame value in a single integer (enum).
/// The least significant 16 bits are used to store the middlegame value and the
/// upper 16 bits are used to store the endgame value. We have to take care to
/// avoid left-shifting a signed int to avoid undefined behavior.
enum Score : int { SCORE_ZERO };

constexpr Score make_score(int mg, int eg) {
  return Score((int)((unsigned int)eg << 16) + mg);
}

/// Extracting the signed lower and upper 16 bits is not so trivial because
/// according to the standard a simple cast to short is implementation defined
/// and so is a right shift of a signed integer.
inline Value eg_value(Score s) {
  union { uint16_t u; int16_t s; } eg = { uint16_t(unsigned(s + 0x8000) >> 16) };
  return Value(eg.s);
}

inline Value mg_value(Score s) {
  union { uint16_t u; int16_t s; } mg = { uint16_t(unsigned(s)) };
  return Value(mg.s);
}

#define ENABLE_BASE_OPERATORS_ON(T)                                \
constexpr T operator+(T d1, int d2) { return T(int(d1) + d2); }    \
constexpr T operator-(T d1, int d2) { return T(int(d1) - d2); }    \
constexpr T operator-(T d) { return T(-int(d)); }                  \
inline T& operator+=(T& d1, int d2) { return d1 = d1 + d2; }       \
inline T& operator-=(T& d1, int d2) { return d1 = d1 - d2; }

ENABLE_BASE_OPERATORS_ON(Score)

/// Only declared but not defined. We don't want to multiply two scores due to
/// a very high risk of overflow. So user should explicitly convert to integer.
Score operator*(Score, Score) = delete;

/// Division of a Score must be handled separately for each term
inline Score operator/(Score s, int i) {
  return make_score(mg_value(s) / i, eg_value(s) / i);
}

/// Multiplication of a Score by an integer. We check for overflow in debug mode.
inline Score operator*(Score s, int i) {

  Score result = Score(int(s) * i);

  assert(eg_value(result) == (i * eg_value(s)));
  assert(mg_value(result) == (i * mg_value(s)));
  assert((i == 0) || (result / i) == s);

  return result;
}

我理解加法、减法和求反的原理，但我无法理解乘法。如何将整数相乘才能正确地将残局得分和中局得分相乘？

Answer 1

这是一个证明，假设您已经理解了加法的原理。

\n

它涉及一些代数，所以这里有一些方便的符号。除非另有说明，所有变量均为带符号的 16 位值，即 2 的补码表示形式。

\n

S(eg,mg) = [eg - neg(mg), mg]

\n

这eg是游戏结束的得分，mg是游戏中期的得分，[,]显示了打包到 32 位 2 的补码有符号整数中的值的位。最重要的位位于左侧。S(eg,mg)是这些分数的表示。这里如果x为负则为1，否则为0，这样就满足了如果x为负则高位neg(x)的表示减1的要求。egmg

\n

这是make_score应该做的（例如错误 \xe2\x80\x94 它与eg_valuenegative不一致mg）。

\n

我们想要证明，对于任何 32 位有符号整数，i乘以S(eg,mg)模型i乘以eg和，可以精确地表示为mgi

\n

(T)i*S(eg,mg) = S(i*eg, i*mg)其中参数中使用 16 位乘法。

\n

证明： \n如果 i=0，这是显而易见的。\n假设 i>0 并且加法有效，即添加表示会添加其残局分数并添加其中局分数。即假设

\n

(A)S(eg1,mg1) + S(eg2,mg2) = S(eg1+eg2,mg1+mg2)对于任何论点。

\n

然后重复使用 (A) 建立 (T)，如下所示。

\n

i*S(eg,mg) \n        // sum of i copies of S(eq,mq)\n    = S(eg,mg) + S(eg,mg) + S(eg,mg) + ... + S(eg,mg)\n        // (A) on first two terms\n    = S(eg+eg,mg+mg) + S(eg,mg) + ... + S(eg,mg)\n    = S(2*eg,2*mg) + S(eg,mg) + ... + S(eg,mg)\n        // (A) on first two remaining terms\n    = S(2*eg+eg,2*mg+mg) + ... + S(eg,mg)\n    = S(3*eg,3*mg) + ... + S(eg,mg)\n        // ...\n    = S(i*eg,i*mg)\n\n

\n

所以现在 (T) 对于除了负值以外的所有值都成立i。

\n

假设i < 0, 并让i = -j. 然后

\n

i*S(eg,mg) \n    = (-1)*j*S(eg,mg)\n        // j is positive\n    = (-1)*S(j*eg,j*mg)\n       // if (T) works for (-1)\n    = S((-1)*j*eg,(-1)*j*mg)\n    = S((-j)*eg,(-j)*mg)\n    = S(i*eg,i*mg)\n

\n

因此 (T) 对于负数i成立，前提是它对于 成立i = -1，这在下面证明。

\n

这是问题的关键：按 (-1) 进行缩放，即证明-S(eg,mg) = S(-eg,-mg)。下面的证明完成了(T)的证明，解决了问题。这是论据：

\n

-S(eq,mq) = -[eg - neg(mg), mg]\n

\n

我们想证明这等于

\n

S(-eg,-mg) = [(-eg) - neg(-mg), (-mg)]\n

\n

这里有一些代数可以做到这一点。它充分利用了众所周知的 2 的补码恒等式-a = ~a + 1，即算术负数比按位负数多 1。

\n

-[eg - neg(mg), mg]\n            // `-a = ~a + 1`\n        = ~[eg - neg(mg), mg] + 1\n            // ~ is bitwise\n        = [~(eg - neg(mg)), ~mg] + 1\n            // if mg=0 the carry on adding 1 will propagate to the upper bits\ncase1: mg=0\n[~(eg - neg(mg)), ~mg] + 1\n           // neg(mg) = 0\n        = [~eg, ~mg] + 1\n            // ~mg is a bit pattern of all ones\n        = [~eg + 1, ~mg + 1]\n            // `~a = -a - 1`\n        = [-eg, -mg]\n            // neg(-mg)=0 because mg=0\n        = [(-eg) - neg(-mg), (-mg)] \n        = S(-eg,-mg) as desired.\ncase2: mg\xe2\x89\xa00\n[~(eg - neg(mg)), ~mg] + 1\n            // carry does not propagate to upper bits\n        = [~(eg - neg(mg)), ~mg + 1]\n            // `~a = -a - 1`\n        = [-(eg - neg(mg)) - 1, -mg]\n        = [-eg - (1 - neg(mg)), -mg]\n            // neg(-mg) = 1 - neg(mg) for mg\xe2\x89\xa00\n        = [(-eg) - neg(-mg), (-mg)]\n        = S(-eg,-mg) as desired.\n

\n