Algoritmo para la copia de N bits en la posición arbitraria de uno a otro int

Question

Un problema interesante que he estado reflexionando sobre los últimos días es cómo copiar los bits de un entero en otro número entero en una posición dada en el número entero de destino. Entonces, por ejemplo, dado el entero de destino 0xdeadbeef y el entero de origen 0xabcd, la idea sería obtener un resultado de 0xabcdbeef (dada una posición de destino de 16 bits) o 0xdeabcdef (dada una posición de destino de 8 bits).

Con la limitación arbitraria de evitar condicionales o bucles (permitiendo a mí mismo para usar Simplemente operaciones matemáticas/bit a bit), he desarrollado la siguiente función (C++)

int setbits(int destination, int source, int at, int numbits) 
{ 
    int ones = ((1<<(numbits))-1)<<at; 
    return (ones|destination)^((~source<<at)&ones); 
} 

donde at es el lugar donde los bits de fuente debe ser copiado en el número de destino (0-31) y numbits es el número de bits que se copia desde source (1-32). Por lo que puedo decir, este algoritmo funciona para todos los valores excepto at = 0 y numbits = 32 (el caso en el que el entero de origen se sobreescribe entero) debido al hecho de que 1 < < 32 resultados en 1 (ya que el cambio se envuelve alrededor) en oposición a 0.

Mis preguntas son:

1. cómo es esto normalmente hecho? ¿Hay algún algoritmo particularmente notable utilizado (por notable, estoy preguntando si hay trucos particularmente eficientes que se pueden utilizar para hacer esto)?
2. funciona mi algoritmo, así como creo que no (es decir, funciona para todos los valores excepto a = 0 y numbits = 32)?
3. relacionados a 1), ¿hay alguna manera de hacer esto sólo con operadores matemáticos/bit a bit? El algoritmo para todos los valores es trivial utilizando condiciones o bucles, por lo que no estoy interesado en eso.

El diseño del algoritmo suele ser un punto débil para mí, así que no tengo idea de si mi algoritmo es "tan bueno como se puede" cuando solo se utilizan operaciones matemáticas/bit a bit. Gracias

Answer 1

no creo que es el caso de que 1 < < 32 envolturas (de lo contrario, ¿por qué doesn 't 2 < < 31 también envolver?), en su lugar, creo que el módulo interno 32 se aplica al segundo operador, por lo que 1 < < 32 es en realidad equivalente a 1 < < 0. Además, considere cambiar los tipos de parámetros de "int "a" unsigned int ". Para obtener el valor de "unos" sin caer en el problema "1 < < 32", usted puede hacer esto:

unsigned int ones = (0xffffffff >> (32-numbits)) << at; 

no creo que hay ningún método "estándar" para este tipo de operación. Estoy seguro de que hay otras maneras de usar operadores bit a bit de diferentes maneras para lograr el mismo resultado, pero su algoritmo es tan bueno como cualquiera.

Dicho esto, sin embargo, la mantenibilidad y la documentación también es importante.Su función se beneficiaría del algoritmo documentado con un comentario, especialmente para explicar cómo usa el XOR bit a bit, que es inteligente, pero no fácil de entender a primera vista.

Answer 2

creo que no podría ser más eficiente. Además, las operaciones bit a bit son mucho más rápidas que cualquier operación algebraica.

Answer 3

Es bastante bueno: Probé esta versión alternativa, pero el suyo era un 30% más rápido en las pruebas:

int[] bits = new int[] {0,1,3,7,15,31,63,127,255,511,1023 
     ,2047,4095,8192,16383,32767,65535,131071,262143,524287 
     ,1048575,2097151,4194303,8388607,16777215,33554431,67108863 
     ,134217727,268435455,536870911,1073741823,2147483647,-1}; 

    public int setbits2(int destination, int source, int at, int numbits) 
    { 
     int ones = bits[numbits + at] & ~bits[at]; 
     return (destination & ~ones) | ((source << at) & ones); 
    } 

Answer 4

No creo que se pueda hacer más eficiente a menos que escriba ensamblador.

Puede mejorar la legibilidad y resolver su problema de desbordamiento de cambiar algunas pequeñas cosas:

int setbits2(int destination, int source, int at, int numbits) 
{ 
    // int mask = ((1LL<<numbits)-1)<<at; // 1st aproach 
    int mask = ((~0u)>>(sizeof(int)*8-numbits))<<at; // 2nd aproach 
    return (destination&~mask)|((source<<at)&mask); 
} 

versión más eficiente ensamblador (VC++):

// 3rd aproach 
#define INT_SIZE 32; 
int setbits3(int destination, int source, int at, int numbits) 
{ __asm { 
    mov ecx, INT_SIZE 
    sub ecx, numbits 
    or eax, -1 
    shr eax, cl 
    mov ecx, at 
    shl eax, cl // mask == eax 
    mov ebx, eax 
    not eax 
    and eax, destination 
    mov edx, source 
    shl edx, cl 
    and edx, ebx 
    or eax, edx 
}} 

• primera aproach: más lento en la arquitectura de 32 bits
• Segundo enfoque: (~ 0u) y (sizeof (int) * 8) se calculan en tiempo de compilación, por lo que no cobran ningún costo.
• 3er enfoque: Se guardan 3 operaciones (accesos a memoria) escribiéndolo en ensamblador pero necesitará escribir ifdefs si desea hacerlo portátil.

Answer 5

generalizada forma GRB-fnieto ...

template <typename T> 
T setbits4(T destination, T source, int at, int numbits) 
{ 
    T mask = (((T)-1)>>(sizeof(T)*8-numbits))<<at; // 4th aproach 
    return (destination&~mask)|((source<<at)&mask); 
} 

Answer 6

// SET OF FUNCTIONS 

//########## BIT - BIT 
template < typename var_t >  inline var_t  bit_V   (uint8_t b)            { return var_t(1) << b; }   // Same as usual macros, but this one converts de variable type, so that you can use it in uint8_t to uint64_t for example. 
template < typename var_t >  inline var_t  bit_get   (const var_t & V , uint8_t b)        { return V & bit_V<var_t>(b); } // Can be used as bool or to get the mask of the bit. 
template < typename var_t >  inline var_t  bit_settled  (const var_t & V , uint8_t b)        { return V | bit_V<var_t>(b); } 
template < typename var_t >  inline var_t  bit_unsettled (const var_t & V , uint8_t b)        { return V &~ bit_V<var_t>(b); } 
template < typename var_t >  inline void  bit_set   (var_t & V , uint8_t b)         {  V |= bit_V<var_t>(b); } 
template < typename var_t >  inline void  bit_unset  (var_t & V , uint8_t b)         {  V &= ~bit_V<var_t>(b); } 
template < typename var_t >  inline void  bit_mod   (var_t & V , uint8_t b , bool set)      { if (set) bit_set(V,b); else bit_unset(V,b); } // compiler will optimize depending on if 'set' is constant. 
template < typename var_t >  inline void  bit_cpy   (var_t & V , const var_t & S , uint8_t b)     { var_t t = bit_get(S,b); V |= t; V &~ t; } 
template < typename var_t >  inline void  bit_cpy   (var_t & V , const var_t & S , uint8_t bV , uint8_t bM) { bit_mod(V,bV,bit_get(S,bM)); } 
/// MULTIPLE BITS: 
template < typename var_t >  inline void  bits_set  (var_t & V , const var_t & S)          { V |= S; } 
template < typename var_t >  inline void  bits_unset  (var_t & V , const var_t & S)          { V &= ~S; } 
/// ONLY WITH UNSIGNED INTS: 'at' parameters are refered to the less significant bit (lsb), starting at 0 index (a byte would have 7 to 0 bits). 
template < typename var_t >    void  bits_cpy  (var_t & V , const var_t & S , uint8_t numBits , uint8_t atlsb = 0 ) { // I choosed not to make this one inline 
                     var_t  mask = (~var_t(0)>>(sizeof(var_t)*8 - numBits))<<atlsb; 
                     bits_unset (V , mask) ; 
                     bits_set (V , S & mask ) ; 
                    } 
template < typename var_t >    void  bits_cpy  (var_t & V , const var_t & S , uint8_t numBits , uint8_t atVlsb , uint8_t atSlsb) { // I choosed not to make this one inline 
                     bits_cpy (V , (atVlsb>atSlsb)?(S<<(atVlsb-atSlsb)):(S>>(atSlsb-atVlsb)) , numBits , atVlsb) ; 
                    } 
template < typename var_t >    var_t  bits_cpyd  (const var_t & V , const var_t & S , uint8_t numBits , uint8_t atlsb = 0 ) { 
                     var_t r = V; 
                     bits_cpy (r,S,numBits,atlsb); 
                     return r; 
                    } 
template < typename var_t >    var_t  bits_cpyd  (const var_t & V , const var_t & S , uint8_t numBits , uint8_t atVlsb , uint8_t atSlsb) { 
                     var_t r = V; 
                     bits_cpy (r,S,numBits,atVlsb,atSlsb); 
                     return r; 
                    } 

//########## BIT - BIT - EXAMPLE OF USE WITH THE MOST RELEVANT FUNCTIONS: 
// I used them inside functions, to get/set two variables inside a class, u and c 

       void    u_set    (edrfu_t u)  {   bits_cpy <uint32_t> (CFG  , u   , 8  , 2    ,0    );} 
       edrfu_t    u_get    ()     { return bits_cpyd <uint32_t> (0   , CFG  , 8  , 0    ,2    );} 
       void    c_set    (edrfc_t c)  {   bits_cpy <uint32_t> (CFG  , c   , 2 );} 
       edrfc_t    c_get    ()     { return bits_cpyd <uint32_t> (0   , CFG  , 2 );} 

Answer 7

uint32_t copy_bits (DST uint32_t, uint32_t src, uint8_t end_bit, uint8_t start_bit)

{

uint32_t left, right, mask, result; 

if (end_bit <= start_bit) 
{ 
    printf("%s: end_bit:%d shall be greater than start_bit: %d\n", __FUNCTION__, end_bit, start_bit); 
    return 0; 
} 

left = ~0; // All Fs 
right = ~0; 
result = 0; 
left >>= ((sizeof(uint32_t)*8) - end_bit); // Create left half of mask 
right <<= start_bit; // Create right half of mask 
mask = (left & right); // Now you have the mask for specific bits 
result = (dst & (~mask)) | (src & (mask)); 
printf("%s, dst: 0x%08x, src: 0x%08x, end_bit: %d, start_bit: %d, mask: 0x%08x, result: 0x%08x\n", 
     __FUNCTION__, dst, src, end_bit, start_bit, mask, result); 

return result; 

}