Setting and clearing multiple bits

[Torbjorn Granlund]

Roberto Bagnara <bagnara at cs.unipr.it> writes:

  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);
  
     //! Clears the bits of \p x from position \p k (included) onward.
     void clear_from(mpz_t x, unsigned long k);
  
  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()?

We don't have any good functions for this today.

You can either set or clear bits individually (mpz_setbit, mpz_clrbit,
mpz_combit), or use the bitwise logical operations (mpz_and, mpz_ior,
mpz_xor) using temporary mask variables.

I think we should extend GMP with more operations in this area.
Here is a suggested interface:

void         mpz_bfset   (mpz_t r, bitcnt_t pos, bitcnt_t len)
void         mpz_bfclr   (mpz_t r, bitcnt_t pos, bitcnt_t len)
void         mpz_bfcom   (mpz_t r, bitcnt_t pos, bitcnt_t len)
// Set (clear, complement) a bit field in r specified by pos,len.

void         mpz_bfins   (mpz_t r, bitcnt_t pos, bitcnt_t len, const mpz_t u)
void         mpz_bfins_ui(mpz_t r, bitcnt_t pos, bitcnt_t len, unsigned long u)
// Insert u into a bit field in r specified by pos,len.

void         mpz_bfext   (mpz_t r, const mpz_t u, bitcnt_t pos, bitcnt_t len)
// Extract a bit field from u at pos of length len and put this in r.

unsigned long mpz_bfext_ui(const mpz_t u, bitcnt_t pos, bitcnt_t len)
// Extract a bit field from u specified by pos,len and return it.
// It len > the bit count of unsigned long, the value will be truncated.

Analogously to the bitwise logical functions, negative operands should
behave like if two's complement were used (GMP uses sign+magnitude).
This means that negative values inserted should behave as if extended
with an infinite number of ones to the left.  This is true for both
input and output.

For example,

  mpz_set_si (u, -1);
  mpz_bfclr (u, 70, 5)

should put -0x7c00000000000000001 onto u.

If somebody decides to work on this project, please let the list know.
Implementations that do not properly handle negative mpz_t numbers are
not useful.

-- 
Torbjörn