Bit flip only function?

Viktor Kletzhändler vkletzhaendler at swissonline.ch
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
--vk






More information about the gmp-discuss mailing list