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