Setting and clearing multiple bits

[Vincent Diepeveen]

Hi Robert,

Does this untested code compile and work?

/* set least significant bits to one from bit 0 to bit k-1,
  * it is not functioning when number of bits is
  * bigger than we have limbs in use
  * (regardless of allocation size)
  */
void set_until(mpz_t x, unsigned long k)
{
   int i = 0,
    #if GMP_LIMB_BITS == 64
    nlimbs = ((k+63) >> 6),
    mask = (int)(k&63),
    #else
    nlimbs = ((k+31) >> 5),
    mask = (int)(k&31),
    #endif
    limbsminus1 = nlimbs - 1;

   if( x->_mp_size|((x->_mp_size-nlimbs)>>31) )
   {
     return;
   }

   while( i < nlimbsminus1 )
   {
     x->_mp_d[i] = (unsigned long)-1;
     i++;
   }

   x->_mp_d[i] |= (1 << mask) - 1;
}

/* this is the same as a mpz_tdiv_r_exp2
  * clear most signficant bits starting at bit k
  */
void clear_from(mpz_t x, unsigned long k)
{
   int
     #if GMP_LIMB_BITS == 64
     nlimbs = ((k+63) >> 6),
     mask = (int)(k&63),
     #else
     nlimbs = ((k+31) >> 5),
     mask = (int)(k&31),
     #endif
     i = nlimbs-1;

   if( nlimbs > x->_mp_size )
   {
     return;
   }

   x->_mp_d[i] &= (unsigned long)-1 ^ ((1 << mask) - 1);
   x->_mp_size = nlimbs;
}

Best
Regards,

Vincent

email: diep at xs4all.nl
skype,aim,google-chat ==> diepchess (voice+webcam at skype only)
msn: diepchess at hotmail.com (do not email there please)

On Sep 4, 2008, at 3:48 PM, Vincent Diepeveen wrote:

>
> On Sep 4, 2008, at 10:43 AM, Roberto Bagnara wrote:
>
>>
>> Hi there,
>>
>> I need to efficiently implement two functions:
>>
>>    //! Sets the bits of \p x up to position \p k (included).
>>    void set_until(mpz_t x, unsigned long k);
>>
>
> Good afternoon,
>
> assuming 64 bits arithmetic:
>
> so if k=5 you want to OR with something like:
>
> firstlimb |= 0b00000000....000000011111;
>
> if k is bigger than 63 you want to set entire limbs to  
> 0b1111111...1111111.
>
> and you want to AND the first few with
>
> unsigned int maskbits = k&63; // replace by 31 for 32 bits
>
> (1<<maskbits) - 1;
>
>>    //! Clears the bits of \p x from position \p k (included) onward.
>>    void clear_from(mpz_t x, unsigned long k);
>
> Hmm maybe it can be done faster than this:
>
> First a mask for the last few bits:
>
> 0b11111111..11111111100000
>
> (unsigned long)-1 ^ ((1<<maskbits)-1);
>
> Lemme fiddle a bit here to get you the correct code that compiles.
>
> Vincent
>
>> For the secone one, I currently have:
>>
>> inline
>> clear_from(mpz_t x, unsigned long k) {
>>    mpz_tdiv_r_2exp(x, x, k);
>> }
>>
>> Is this the best I can do?  And how could I efficiently
>> compute set_until()?
>> All the best,
>>
>>     Roberto
>>
>> -- 
>> Prof. Roberto Bagnara
>> Computer Science Group
>> Department of Mathematics, University of Parma, Italy
>> http://www.cs.unipr.it/~bagnara/
>> mailto:bagnara at cs.unipr.it
>> _______________________________________________
>> gmp-discuss mailing list
>> gmp-discuss at swox.com
>> https://gmplib.org/mailman/listinfo/gmp-discuss
>>
>