当没有位移运算符时进行位移操作

Question

我需要在VBScript中实现一个校验和(CRC16 CCITT)，以验证文件的内容。

由于VBScript中没有提供位移操作符，所以我必须依靠乘以2和除以2等简单的数学运算来计算校验和。但是这种方法对于负数不起作用。

我进行了一些测试，发现VBScript使用补码表示其16位整数。

Q1: 有人能够确认VBScript使用的是补码表示法吗？我在MSDN网站上没有找到精确的信息。

Q2: 当使用补码表示法时，是否可以使用简单的数学运算进行位移(左移和右移)？

.

非常感谢您的帮助，以下是我在VBScript中实现右移的代码:

Function rightShift(value,bits)
    Dim res

    res = 65535 AND value

    If value>=0 Then
       res = res \ (2^bits)
    Else If value=-1 Then
             res = rightShift(res + 32768, bits - 1)
         Else
             res = rightShift(value \ 2 + 32768, bits - 1)
         End If
    End If

    rightShift = res AND 65535
End Function 

关于上述代码的说明：value有时会超过16位，因此我必须掩盖未使用的位以避免溢出（AND 65535）。

- Jerome

---

非常感谢您分享您的代码！我需要完全相同的东西，只是32位而已，使用您的代码很容易实现。 :) 我正在实现CRC32。 :) - Filip Vondrášek

Answer 1

在二进制补码算术中，负值唯一的影响是在进行除以2位移右侧时发生：预期的位移将会发生，但也会在最高有效位（MSB）位置引入一个新的1位“保持值为负”——除非原始值为-1，在这种情况下所有位都变成0。因此，为了纠正这个问题，请尝试以下伪代码：

rightshift(x) {
    if x >= 0 return x / 2;
    if x < -1 return x / 2 - MINVAL;    # Strip out sign bit
    # x must be -1, i.e. "all bits on"
    return x - MINVAL;
}

MINVAL应该是仅由最高位为1，其他所有位为0组成的值，对于16位来说是-32768。（因为它将是使用二进制补码表示时最小的可表示负数）。有趣的是，在上述伪代码中加上MINVAL与减去MINVAL一样有效，因为在二进制补码算术中，x-y=x+NOT(y)+1，而MINVAL==NOT(MINVAL)+1。左移（乘2）对于负数和正数同样有效。

- j_random_hacker

Answer 2

这不是答案，而是一条评论。@j_random_hacker 给出的答案对我有用。但在像C#这样执行整数除法的语言中（假设由于某种原因你无法使用内置的右移操作符），当x不是偶数时，需要向上舍入。

static int MINVAL = (int) -0x80000000;
    static int ShiftRight(int n,int bits)
    {
        //if (n >= 0) return n / (int)Math.Pow(2, bits);
        //double temp = n / Math.Pow(2, bits);
        //int r  = (int) Math.Floor(temp);
        //return r;
        if (n >= 0) return n / 2;
        if (n < -1) return (int)Math.Round(n / (double)2, MidpointRounding.AwayFromZero) - MINVAL;//+ (n%2==0?0:-1);    // Strip out sign bit
        // x must be -1, i.e. "all bits on"
        return n - MINVAL;
    }

现在，C#已经内置了位移运算符，所以这只是为了教育目的。

- argsv

Answer 3

这很慢，试试这个。下面的代码可以用于值>=0，但对于大于14位的位移将抛出数组下标越界异常：

dim ShiftArray
ShiftArray = Array(1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
1024,2048,4096, 8192, 16384)

' example usage
dim num
num = 17
num = num * ShiftArray(2) ' left shift 2 bits
num = num / ShiftArray(3) ' right shift 3 bits

左移操作时需要乘以位移的比特数，右移则需要除以比特数。

此数组适用于16位整数。

对于32位整数，当位移 > 30 时，该数组会抛出越界错误，可使用以下数组代替：

dim ShiftArray
ShiftArray = Array(1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,   
2048,4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,
1048576, 2097152, 4194304, 8388608, 16777216, 33554432,
67108864, 134217728, 268435456,  536870912, 1073741824)

- Jeff Landers