Bit flip only function?

David Gillies daggillies at gmail.com
Sun Jul 20 21:25:31 UTC 2014


Err, I mean f(0) = 0. That would arise naturally from the definition of the
function if mpz_sizeinbase(0,2) were zero, but it is one. Apart from that
the function is easy to implement in terms of mpz_mul_2exp and mpz_xor.
Note that f(x) < x since the MSB of x is cleared.  i guess a simple-minded
implementation would look something like:

void bitflip(mpz_t rop,mpz_t op)
{
   mpz_t                mask;

   if(!mpz_cmp_ui(op,0UL))
      {
      mpz_set_ui(rop,0);
      return;
      }

   mpz_init_set_ui(mask,1UL);
   mpz_mul_2exp(mask,mask,(mp_bitcnt_t)mpz_sizeinbase(op,2));
   mpz_sub_ui(mask,mask,1UL);
   mpz_xor(rop,op,mask);

   mpz_clear(mask);
}



On Sun, Jul 20, 2014 at 12:27 PM, David Gillies <daggillies at gmail.com>
wrote:

> If I understand correctly, what Viktor is looking for is a function that
> (ugly notation, sorry) performs f: mpz-> mpz, z -> z XOR
> (2^mpz_sizeinbase(z,2) -1). This is surjective but not injective so f(0)
> would either be undefined or, more benignly, a fixed point f(0) = f(0).
>
>
> On Sun, Jul 20, 2014 at 11:23 AM, Torbjörn Granlund <tg at gmplib.org> wrote:
>
>> Viktor Kletzhändler <vkletzhaendler at swissonline.ch> writes:
>>
>>   mpz_com seems to do more than flipping.
>>
>> We might not understand what "flipping" might mean.  mpz_com
>> computes the one's complement.
>>
>>   For example, for a base-2 number
>>   mpz_com ( 1111 1111 ) returns ( -1 0000 0000 )
>>   whereas I would like _dcom ( 1111 1111 ) returns ( 0 ).
>>
>>   Am I missing something?
>>
>> So "flipping" means f(11111111) = 0, i.e., 8 consecutive ones should map
>> to 0.  I assume the function "flipping" should be a bijection, so no
>> other value x should have f(x) = 0.  Perhaps f(f(x)) = x should hold for
>> any value x?
>>
>> Then, what should f(1), f(11), f(111), ... yield?  What's so special
>> about 11111111?
>>
>> --
>> Torbjörn
>> Please encrypt, key id 0xC8601622
>> _______________________________________________
>> gmp-discuss mailing list
>> gmp-discuss at gmplib.org
>> https://gmplib.org/mailman/listinfo/gmp-discuss
>>
>
>
>
> --
> David Gillies
> San Jose
> Costa Rica
>



-- 
David Gillies
San Jose
Costa Rica


More information about the gmp-discuss mailing list