Bit flip only function?

[Pedro Gimeno]

Viktor Kletzhändler wrote, On 2014-07-21 00:11:
> "Flipping" means applying the equivalent of the C bitwise "~" operator on the mantissa of an mpz (as indicated in the original post).
> 
> The ~ operator is only defined for fixed width data types (K&R, second edition, p. 48). For such types, it calculates the "one's complement":
> 
> "The unary operator ~ yields the one's complement of an integer, that is, it converts each 1-bit into a 0-bit and vice versa." (op. cit., p. 49). 

Problem is, MPZ numbers are not fixed width data types. They are defined
as being arbitrary integers of any size (for most practical purposes
anyway).

Now, when flipping the bits of the binary number 0 (with unbound, not
fixed, size) you get: (infinite 1's)...111

Internally, GMP represents that number as -1, but you shouldn't care
about what the internal representation is. The logical operators treat
it as an infinite string of 1's.

For example, for that number, mpz_tstbit gives 1 for every possible bit
index.

If you use `mpz_and` on that number with another, you get the second
number, as every bit that was set in the second number will be ANDed
with an 1, because the first number has 1's everywhere (from `mpz_and`'s
perspective).

Likewise, if you AND the result of `mpz_com` with a positive power of
two minus 1, that is, with a finite-length string of 1's that starts
from the least significant bit, you will get a fixed-size one's
complement similar to the ones that you seem to want.

> mpz_com seems to calculate something like the two's complement of the operand (as indicated in the manual). It assumes some fixed width type (maybe a 16-bit type in this example) and calculates the two's complement representation (maybe "11111111 00000000" in this example), which would explain the result "-1 0000 0000" (aka decimal -256 in two's complement representation).

This is wrong on several accounts.

- The manual clearly indicates that `mpz_com` performs the ONE'S
complement, not the two's complement.
- It does not assume any fixed width type. It assumes an arbitrary size.
I think this is the main source of your confusion.
- The use of two's complement for binary operations actually means that
the number -100000000 binary is treated by the logical operators as:
(infinite ones)...1100000000.
- The fact that it's negative is an implementation detail that should
not affect you. Negative numbers are treated as having a leading
infinite string of 1's. A leading infinite string of 1's is not what you
want if you're working with fixed size unsigned numbers: you have to
mask out unwanted 1's.

> If there is no "~" function available, I have to use my own code.

There is. Try to understand the above. If you want the result to be a
fixed size unsigned integer, mask the result with a suitable constant
that is the (desired size)'th power of two minus 1, using `mpz_and`.

For example, if your input is the binary number 1011101100010, and you
want the binary complement up to say 32 bits, first perform `mpz_com` on
it, then perform `mpz_and` of the result with the binary number
11111111111111111111111111111111 (2^32-1). You will get the result
(infinite zeros)...00011111111111111111110100010011101 which is the
positive decimal 4294961309, and that seems to be what you want.