Бит сдвиг, когда нет ... Оператор сдвига бит

Question

Я должен реализовать контрольную сумму (CRC16 CCITT), чтобы проверить содержимое файла. Контрольную сумму довольно просто реализовать на C или Java благодаря < < и >> операторам и множеству примеров, доступных в сети.

Дело в том, что мои вычисления контрольной суммы должны быть реализованы в VBScript.

Опыт работы с этим языком почти невозможен, но, по моему мнению, в VBScript ничего не предусмотрено для смещения бит. Поэтому я полагаюсь на умножения и деления на на два. Это хорошо работает, за исключением отрицательных значений.

Я проверил несколько тестов, и я считаю, что VBScript обрабатывает его 16-битные целые числа с дополнением двух.

Q1: Может ли кто-нибудь подтвердить это (дополнение двух в VBScript)? Я не нашел точной информации с веб-сайта MSDN.

Q2: Можно ли выполнить сдвиг вправо (вправо и влево) с помощью простых математических операций, когда отрицательное число кодируется с дополнением 2?

.

Большое спасибо, я бы очень хотел избежать kludge, как иметь дело с целыми числами как массивы '1' и '0' или вызывать некоторые приложения java/c из VBScript.

EDIT спасибо за помощь, найти ниже моей реализации сдвига вправо в 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 

Примечание о коде выше: значение иногда превышая 16 бит поэтому мне пришлось маскировать неиспользуемые биты, чтобы избежать переполнения (AND 65535).

Answer 1

В арифметике с двумя дополнениями единственное воздействие, которое отрицательные значения имеют при делении на 2 на сдвиг вправо: будет иметь место предполагаемый сдвиг вправо, но он также будет вводить новый 1-бит в наиболее значительном бите (MSB) в положение «сохранить значение отрицательное» - если исходное значение не было -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 должен быть значение, представление которого состоит только из MSB и всех остальных битов, которое составляет -32768 для 16 бит. (Так названо, потому что это будет самое отрицательное представимое число с использованием двух'-дополнений.) Интересно, что добавление MINVAL работает так же, как и вычитает его в вышеуказанном псевдокоде, поскольку в двухфазной арифметике x - y = x + NOT(y) + 1 и MINVAL == NOT(MINVAL) + 1.

Смещение влево с использованием умножения на 2 для отрицательных чисел так же хорошо, как для положительных.

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# имеет встроенные операторы сдвига, поэтому это всего лишь образовательная цель.

Answer 3

Это очень медленно, попробуйте это. Следующие работы для значений> = 0, но будет сгенерирует индекс массива вне границ для bitshifts> 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-разрядных целых чисел массив будет Сбрось из границ массива подстрочный для bitshifts> 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)