Bitwise operations on sign-magnitude big integers

Question

I am writing a simple BigInteger type in Delphi. This type consist of an array of unsigned 32 bit integers (I call them limbs), a count (or size) and a sign bit. The value in the array is interpreted as absolute value, so this is a sign-magnitude representation. This has several advantages, but one disadvantage.

The bitwise operations like and, or, xor and not have two's complement semantics. This is no problem if both BigIntegers have positive values, but the magnitudes of negative BigIntegers must be converted to two's complement by negation. This can be a performance problem, since if we do, say

C := -A and -B;

then I must negate the magnitudes of A and B before the and operation can be performed. Since the result is supposed to be negative too, I must negate the result too to get a positive magnitude again. For large BigIntegers, negating up to three values can be a considerable performance cost.

Mind you, I know how to do this and the results are correct, but I want to avoid the slowness caused by the necessary negations of large arrays.

I know of a few shortcuts, for instance

C := not A;

can be achieved by calculating

C := -1 - A;

which is what I do, and the result is fine. This makes not as performant as addition or subtraction, since it avoids the negation before (and after) the operation.

Question

My question is: are there similar laws I can use to avoid negating the magnitudes of "negative" BigIntegers? I mean something like the calculation of not by using subtraction?

I mean simple or not-so-simple laws like

not A and not B = not (A or B) // = is Pascal for ==
not A or not B = not (A and B)

but then for -A and/or -B, etc. I do know that

(-A and -B) <> -(A or B) // <> is Pascal for !=

is not true, but perhaps there is something similar?

I simply can't find any such laws that relate to negative values and bitwise operations, if they exist at all. Hence my question.

Answer 1

Last time I checked negation worked like this:

-A = not(A) + 1; or
-A = not(A - 1);
that means that
-A and -B = not(A - 1) and not(B - 1)

if we add another NOT at the front than we can replace the and not with an or

not(-A and -B) = not(not(A - 1) and not(B - 1)) =
(A - 1) or (B - 1)   

We still need to do an expensive not at the end, but because not is so close to - we can cheat and replace the expensive not with a cheap - like so:

-(-A and -B) = (A-1) or (B-1) + 1;

And finally the outcome will be:

(-A and -B) = -((A-1) or (B-1) + 1);   

This should be much faster than flipping all the bits.

This will be very cheap to implement because:

1. Negation is a simple bit flip on your sign byte.
2. +1/-1 will run out of carry/borrow bits very soon in the overwelming amount of cases (only 1/2^32 cases will carry/borrow to the next limb).

The same goes for or; not or is very close to and.

Answer 2

My question is: are there similar laws I can use to avoid negating the magnitudes of "negative" BigIntegers?

Yes, and I did before what you want to do - see here, lines 105 - 115 (or better download the repository). Strange enough I also use the term 'Limb".

For example arrAndTwoCompl computes bitwise and of positive and negative, arrAndTwoCompl2 computes bitwise and of 2 negatives.

I've taken these 'laws' from GMP sources.

Don't reinvent big integers, just use them.