Отрицательные числа со сдвигом влево *всегда* заполняются 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?


c++ .net biginteger bit-shift twos-complement
person halfbit    schedule 10.03.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Из BigInteger.LeftShift документации оператора:

В отличие от операции побитового сдвига влево с целочисленными примитивами, метод LeftShift сохраняет знак исходного значения BigInteger.

Итак, .NET гарантирует поведение, которое вы видите.

Я не очень хорошо знаком с библиотеками bignum, но в документации для функции OpenSSL BIGNUM BN_lshift()` говорится:

BN_lshift() сдвигает a влево на n бит и помещает результат в r ("r=a*2^n"). BN_lshift1() сдвигает a влево на единицу и помещает результат в r ("r=2*a").

Поскольку операция определяется в терминах умножения на степень двойки, если вы преобразуете полученное BIGNUM в число с дополнением до двух (я понятия не имею, как BIGNUM представляет числа внутри), вы увидите поведение, аналогичное .NET.

Я не удивлюсь, если другие библиотеки bignum будут вести себя так же, но вам действительно нужно проверить документы, если вы хотите зависеть от поведения. Однако, поскольку сдвиг очень похож на умножение или деление на степени двойки, вы, вероятно, можете получить «переносимое» поведение, используя соответствующее умножение или деление вместо сдвига. Тогда все, что вам нужно убедиться, это то, что вы можете получить преобразование в представление дополнения до двух (что является проблемой, которая действительно не зависит от поведения операции сдвига).

person Michael Burr    schedule 11.03.2013

arrow_upward
1
arrow_downward

Должен ли я всегда ожидать, что подобная операция битового сдвига будет действовать таким образом?

Вы должны, если рассматриваемый числовой формат использует дополнение до двух для представления отрицательных чисел (и многие делают). Чтобы сформировать дополнение числа до двух, вы инвертируете все биты и добавляете один, например:

23 is represented as 00010111
-23 is represented as 11101001 (that is, 11101000 + 1)

Кроме того, когда вы конвертируете тип в более крупный тип, значение обычно расширяется по знаку, т. е. самый левый бит расширяется до дополнительных битов в более крупном типе. Это сохраняет знак числа.

Так что да, числовые представления довольно часто «заполняются» 1 для числовых значений.

person Caleb    schedule 11.03.2013

arrow_upward
0
arrow_downward

10000010 сначала изменяется на большую ширину. В данном случае 4 байта:

10000010 --> 11111111 11111111 11111111 10000010

Вы получаете 1 с слева, так как число отрицательное.

Теперь сдвиг влево просто вставляет 0 справа и выбрасывает биты слева:

11111111 11111111 11111111 10000010 << 16 -->
11111111 10000010 00000000 00000000
person Shahbaz    schedule 11.03.2013
comment
Это стандартное поведение С++? IIRC определяется реализацией, а не стандартным поведением. - person Richard J. Ross III; 11.03.2013
comment
На самом деле это неопределенное поведение для сдвига влево отрицательного числа в C или C++. - person Michael Burr; 11.03.2013
comment
Ага, см. вызывает ли операция сдвига влево неопределенное поведение, когда левая сторона oper"> stackoverflow.com/questions/3784996/ - person MSalters; 11.03.2013
comment
@RichardJ.RossIII, я этого не знал. Я не имел в виду использовать эту фразу в соответствии со стандартом, я скорее хотел сказать, что это вещь C++ и не имеет ничего общего с .net или biginteger. Удалил все-таки. - person Shahbaz; 11.03.2013