Setting and clearing multiple bits
Vincent Diepeveen
diep at xs4all.nl
Mon Sep 8 08:20:17 CEST 2008
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
>>
>
More information about the gmp-discuss
mailing list