左移操作的结果的数学表达

2023-04-04 10:07 2023-04-04 15:15 作者: xmh0511

对于一个给定的值存储在具有`N`位的对象中，可以通过二进制表示法表示为:
> AN * 2N-1 + AN-1 * 2N-2 + ... + A1 * 20

如果对该数进行 `<< X`的操作，就等同于该数乘以2X，结果通过二进制表示法可以表示为:
> Ss = AN * 2N-1+X + AN-1 * 2N-2+X + ...+ AN - X + 1 * 2N + AN - X * 2N - 1 + ... + A1 * 2X

对于结果`Ss`, 保存在原来的对象中值`Sd`需要满足 `Ss` congruent to `Sd` modulo 2N, 即

> Ss - Sd = K \* 2N => Sd = Ss - K \* 2N

对于无符号整数，Sd ∈ [0, 2N - 1 ], 其中最大值2N - 1的二进制表示为:
> 1 \* 2N - 1 + 1 \* 2N - 2 + ... + 1 \* 20

即 AN+1 2N及以后得系数AN+m(m≥1)都要为0(否则将超过最大值)。则减K\* 2N含义为:
> \- 2N \* ( AN * 2X - 1 + AN-1 * 2X - 2 + ... + AN - X + 1 * 20 ), `N - X + 1` < `N-1`，使得AN+m(m≥1)全为0。则`Sd`的二进制表示为：
>> AN - X * 2N - 1 + ... + A1 * 2X + 0 \* 2X - 1 + ... + 0 \* 20

对于有符号整数， Sd∈[-2N - 1, 2N - 1 -1 ]，最小，最大值的二进制表示
> min: (-1)1 \* 2N - 1 + 0 \* 2N - 2 + ... + 0 \* 20
> 
> max: 0 \* 2N - 1 + 1 \* 2N - 2 + ... + 1 \* 20

所有有效数值的二进制表示则为：
> AN \* (-1)AN \* 2N - 1 + AN - 1 \* 2N - 2 + ... + A1 \* 20

令AN \* (-1)AN 为A'N, 则 A'N = 0 或 -1 使得有效值成立。对于`Ss`, 如果AN - X 为0， 则减K\* 2N含义为
> \- 2N \* ( AN \* (-1)AN * 2X - 1 + AN-1 * 2X - 2 + ... + AN - X + 1 * 20 ), `N - X + 1` < `N-1`，使得AN+m(m≥1)全为0, `Sd`的二进制表示为:
>> AN - X * 2N - 1 + ... + A1 * 2X + 0 \* 2X - 1 + ... + 0 \* 20

如果 AN - X 为 1， 则 减K\* 2N含义为
> \- 2N \* ( AN \* (-1)AN * 2X - 1 + AN-1 * 2X - 2 + ... + AN - X + 1 * 20 ), 使得AN+m(m≥1)全为0, 得到结果Sd', 二进制表示:
>> AN - X * 2N - 1 + ... + A1 * 2X + 0 \* 2X - 1 + ... + 0 \* 20, 又因为 AN - X 为1，还需减掉2N => 使得结果为 Sd, 二进制表示为
>>> (-1) \* 2N - 1 + ... + A1 \* 2X + 0 \* 2X - 1 + ... + 0 \* 20 =>
>>> 
>>> AN - X \* (-1)AN - X \* 2N - 1 + ... + A1 \* 2X + 0 \* 2X - 1 + ... + 0 \* 20

因此 减 K\* 2N的含义为
> \- 2N (AN \* (-1)AN * 2X - 1 + AN-1 * 2X - 2 + ... + AN - X + 1 * 20 + 1)

***

##### 补充说明

~~> \- 2N \* K 是否改变`N`上的系数值~~

~~对于任意`K ≠ 0`，K可以被分解为~~ 
~~> ( 2P - 2Q - R ), R = 0 或 1, 且R = 1时， P和Q ≠ 0~~

~~则 -K\* 2N 为~~
~~> -2N + P + 2N + Q + R \* 2N~~

~~当( 2P - 2Q - R ) ≠ 1，只会修改`Item = min(N+P, N+Q) + 1`及以上的系数值, 其中`Item > N`~~

~~当( 2P - 2Q - R ) = 1, AN - X为1时，S - K\* 2N则可以化简为：~~
~~> -2N + 2N - 1 + Sub => -2N - 1 + Sub~~

~~AN - X任然为1~~

##### 方法二
K \* 2N => 2K \* 2N - 1, 当AN - X为0时，Ss - K \* 2N => (-2K) \* 2N - 1 + Sub, 因为K为整数， 当K等于0，（-2K）为0, 即，N位上的系数任然为0。 否则| -2K | > 0, 一定可以写成 -(2M - 2Q), M, Q ≥ 1，
> -2M+N-1 + 2Q+N - 1， 则有
> M+N-1 > N - 1, Q+N - 1 > N - 1

因此修改的系数一定是 N+1位及以后的。

当AN - X为1时， Ss - K \* 2N => (-2K + 1) \* 2N - 1 + Sub, 因为K为整数，当K = 0时，(-2K + 1) = 1，所以N上的系数任然为1。否则-(2K - 1)表示一个奇数，可以写成-(±2M - 1), 则有
> (-±) 2M + N - 1 + 2N - 1

当M ≥ 2时，M+N - 1一定≥ N + 1，所以修改的是N+2位及以上的系数，N上系数任然为1。 | 2K -1 | ≥ 3,  则 | K | ≥ 2

当 M = 1 时，则K = ±1 则有
> (-±) 2M + N - 1 + 2N - 1
>> \- 2 N + 2N - 1 => (-1) \* 2N - 1
>> 
>> 2N + 2N - 1

任意情况N位上的系数都为1。