Cambio de bit cuando no hay ... operador de desplazamiento de bit

Question

Tengo que implementar una suma de verificación (CRC16 CCITT) para verificar el contenido de un archivo. La suma de comprobación es bastante simple de implementar en C o Java gracias a los operadores < < y >> y a los muchos ejemplos disponibles en la red.

Lo que pasa es que ... mi cálculo de suma de comprobación debe implementarse en VBScript.

Mi experiencia con este lenguaje es casi nula pero desde mi entender, no hay nada provisto para hacer cambios de bit en VBScript. Por lo tanto, confío en multiplicaciones y divisiones por dos. Funciona bien excepto con valores negativos.

Realicé algunas pruebas y creo que VBScript maneja sus enteros de 16 bits con el complemento de dos.

Q1: ¿alguien puede confirmarme esto (complemento de dos en VBScript)? No encontré información precisa del sitio web de MSDN.

Q2: ¿Es posible hacer un cambio de bit (derecha e izquierda) con operaciones matemáticas simples cuando el número negativo está codificado con el complemento de dos?

.

Muchas gracias, me gustaría evitar un problema como tratar con enteros como matrices de '1' y '0' o llamar a alguna aplicación java/c de VBScript.

EDITAR gracias por la ayuda, encontrar a mi aplicación de un desplazamiento a la derecha en 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 

Nota sobre el código anterior: valor era a veces excediendo los 16 bits, por lo tanto tenía que enmascarar el bits no utilizados para evitar el desbordamiento (AND 65535).

Answer 1

En la aritmética de dos complementos, el único impacto que tienen los valores negativos al dividir por 2 para desplazarse a la derecha: se producirá el cambio a la derecha previsto, pero también introducirá un nuevo 1 bit en el bit más significativo (MSB) la posición de "mantener el valor negativo" - a menos que el valor original era -1, en cuyo caso todos los bits se convierten en 0. Entonces, para corregir esto, intente lo siguiente pseudocódigo:

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 debería ser el valor cuya representación consiste solo en MSB activado y todos los demás bits desactivados, que es -32768 para 16 bits. (Llamado así porque será el número representable más negativo usando el complemento de dos.) Curiosamente, agregar MINVAL funciona tan bien como restarlo en el pseudocódigo anterior, ya que en la aritmética de dos complementos, x - y = x + NOT(y) + 1 y MINVAL == NOT(MINVAL) + 1.

Cambios a la izquierda usando multiplicación por 2 para números negativos tan bien como para positivos.

Answer 2

Esto no es una respuesta, pero un comentario. La respuesta dada por @j_random_hacker funcionó para mí. Pero en los lenguajes que realizan divisiones enteras como C# (suponiendo que no se pueda usar el operador de desplazamiento a la derecha incorporado por la razón que sea) se debe redondear cuando x no es par.

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; 
    } 

Ahora sí C# tiene un operador de turno incorporado, por lo que este es solo un objetivo educativo.

Answer 3

Eso es muy lento, intente esto. Las siguientes obras para valores> = 0, pero se lanzar un subíndice de matriz fuera de límites para bitshifts> 14 bits y el código es:

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 

Multiplicar por el número de bits a desplazar de desplazamiento a la izquierda. Divide para el cambio a la derecha. Esta matriz funciona para enteros de 16 bits.

Para enteros de 32 bits de la matriz se Thow fuera de los límites subíndice para bitshifts> 30 y es:

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)