Bitwise operations on big integers

Standard fixed-sized negative integers are stored in two’s complement format; for arbitrary-precision big integers the two’s complement format means infinite size, so internally it is not used. Still bitwise operation on big integers are implemented as if negative big integer values are stored in two’s complement format.

As a result bitwise boolean operations (and, or, xor) applied to big integers produce the same results as with standard fixed-sized integers:

procedure Test1(I, J: Integer);
var
  BigI, BigJ: BigInteger;

begin
  BigI:= I;
  BigJ:= J;
  Assert(BigI and BigJ = I and J);
  Assert(BigI or BigJ = I or J);
  Assert(BigI xor BigJ = I xor J);
end;

There is a difference between standard Delphi integer types and big integers in shift operations. Shift operations on big integers preserve sign. That means any shift applied to negative big integer results in negative big integer (the same is for non-negative values):

procedure Test2(I: BigInteger; N: Cardinal);
begin
  Assert(((I shl N) < 0) = (I < 0));
  Assert(((I shr N) < 0) = (I < 0));
end;

That is a natural consequence of the infinite-sized two’s complement negative values. Shift operations on big integers are arithmetic shifts rather than logical shifts. On the other hand ‘shl’ and ‘shr’ operations on the standard Delphi integer types are implemented as logical shifts and does not preserve sign:

procedure Test3;
var
  I: Integer;

begin
  I:= -1;
  Writeln(I shr 2);   // 1073741823, because 'shr' is logical shift
  I:= 1000000000;
  Writeln(I shl 2);   // -294967296, because of 32-bit overflow
end;

PS: right now TForge does not support bitwise operations on BigInteger type, they will be implemented soon.