Bit flip only function?

Viktor Kletzhändler vkletzhaendler at
Sun Jul 20 22:11:56 UTC 2014

Thanks for the reply.

> We might not understand what "flipping" might mean.  mpz_com
> computes the one's complement.

"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). 

To reiterate, for a binary example argument,
mpz_com ( 1111 1111 ) returns ( -1 0000 0000 ).

Obviously, the result is not the "one's complement" as defined above (which would be "0000 0000" aka zero). 

> So "flipping" means f(11111111) = 0, i.e., 8 consecutive ones should map
>  to 0.  I assume the function "flipping" should be a bijection, ...
>  ... 
> What's so special about 11111111?

Yes. As per definition, the ~ operator maps any full byte(s) to zero. And no, this operation is not bijective. 11111111 is just an example, nothing special. 

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). In this example, mpz_com adds a carry bit to the argument, assuming the argument is a 16-bit integer, although the argument could be an 8-bit integer (aka decimal -1 in two's complement representation) whose ones complement is zero. This breaks the above definition of "one's complement", IMO.

For the "flipping" operation I'm referring to, the most significant 1-bit always defines the width, because "setting the leading 0-bits" is meaningless for infinite width, and because mpz is a sign magnitude, not a two's complement data type. Consequently, the operation is defined only for flip(z), z!=0, so a leading 1-bit is always present (as you can see in the example code).

All mpn_ bitwise logical functions which complement something seem to implement the same "one's complement" behavior as mpz_com (which is not "one's complement" IMHO). The mpz_setbit etc. functions are not efficient. This is not what I'm looking for.

If there is no "~" function available, I have to use my own code. So, is the example code in the original post safe, or are there any pitfalls I'm not aware of?

Thanks for advise

More information about the gmp-discuss mailing list