Setting and clearing multiple bits
Torbjorn Granlund
tg at swox.com
Mon Sep 8 14:38:27 CEST 2008
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
More information about the gmp-discuss
mailing list