Отрицательные числа со смещением влево * всегда * заполняются знаком «1» вместо «0»?
Я независимо изучаю сдвиг битов, портируя некоторые функции C ++ на BigInteger .NET. Я заметил, что когда я сдвинул BigInteger, пустота заполнилась единицами.
Я считаю, что это связано с тем, что отрицательное число хранится в форме комплимента.
BigInteger num = -126;
compactBitsRepresentation = (uint)(int)(num << 16);
Вот что произошло после смены (самый важный бит первый)
10000010 will be shifted 16
11111111100000100000000000000000 was shifted 16
Должен ли я всегда ожидать, что подобная операция сдвига битов будет действовать таким образом? Согласуется ли это с различными языками и реализациями «bigNumber», такими как OpenSSL?
Решение
От BigInteger.LeftShift оператор документы:
В отличие от побитовой операции сдвига влево с целочисленными примитивами,
Метод LeftShift сохраняет знак исходного значения BigInteger.
Таким образом .NET гарантирует поведение, которое вы видите.
Я не очень знаком с библиотеками bignum, но документы для функции OpenSSL BIGNUM BN_lshift () `гласят:
BN_lshift()сдвигает влево на n битов и помещает результат в r («r = a * 2 ^ n»).BN_lshift1()сдвиг влево на единицу и помещает результат в r («r = 2 * a»).
Поскольку операция определяется умножением на степень два, если вы преобразуете полученный BIGNUM в число дополнения до двух (я понятия не имею, как BIGNUM представляет числа внутри), вы увидите поведение, аналогичное .NET.
Я не удивлюсь, если другие библиотеки bignum будут вести себя так же, но вам действительно нужно проверить документы, если вы хотите зависеть от поведения. Однако, поскольку сдвиг очень похож на умножение или деление на степени двух, вы, вероятно, можете получить «переносимое» поведение, используя соответствующее умножение или деление вместо сдвига. Тогда все, что вам нужно, это убедиться, что вы можете получить преобразование в представление дополнения до двух (это проблема, которая действительно не зависит от поведения операции сдвига).
Другие решения
Должен ли я всегда ожидать, что подобная операция сдвига битов будет действовать таким образом?
Вы должны это делать, если рассматриваемый формат чисел использует два дополнения для представления отрицательных чисел (а многие это делают). Чтобы сформировать двоичное дополнение числа, вы инвертируете все биты и добавляете единицу, например:
23 is represented as 00010111
-23 is represented as 11101001 (that is, 11101000 + 1)
Кроме того, когда вы преобразуете тип в больший тип, значение обычно расширяется до знака, то есть крайний левый бит расширяется до дополнительных бит в более крупном типе. Это сохраняет знак числа.
Так что да, довольно часто для числовых представлений «заполняется» 1 для числовых значений.
10000010 сначала изменяется на большую ширину. В этом случае 4 байта:
10000010 --> 11111111 11111111 11111111 10000010
Вы получаете 1 слева, так как число отрицательное.
Теперь левый сдвиг просто вставляет нули справа и выбрасывает биты слева:
11111111 11111111 11111111 10000010 << 16 -->
11111111 10000010 00000000 00000000