Алгоритм для копирования N бит в произвольном положении из одного int в другой
Интересная проблема, о которой я размышлял последние несколько дней, - это копирование целочисленных битов в другое целое число в заданной позиции в целевом целое. Так, например, с учетом целевого целого числа 0xdeadbeef и исходного целого числа 0xabcd, идея заключалась бы в получении результата 0xabcdbeef (с заданной позицией 16 бит) или 0xdeabcdef (с учетом позиции адресата из 8 бит).
При произвольном ограничении избегания условных или петель (позволяя мне использовать только математические/побитовые операции), я разработал следующую функцию (С++)
int setbits(int destination, int source, int at, int numbits)
{
int ones = ((1<<(numbits))-1)<<at;
return (ones|destination)^((~source<<at)&ones);
}
где at - это место, где исходные биты должны быть скопированы в номер назначения (0-31), а numbits - количество бит, копируемых из source (1-32). Насколько я могу судить, этот алгоритм работает для всех значений, за исключением at= 0 и numbits= 32 (случай, когда целое целые назначения переписываются исходным целым) из-за того, что 1 < < lt; 32 приводит к 1 (так как сдвиг обертывается вокруг) в противоположность 0.
Мои вопросы:
- Как это обычно делается? Существуют ли какие-либо особенно заметные алгоритмы (замечательно, я спрашиваю, есть ли особенно эффективные трюки, которые можно использовать для этого)?
- Работает ли мой алгоритм так же хорошо, как я думаю (он работает для всех значений, кроме = 0 и numbits = 32)?
- В связи с 1), есть ли способ сделать это только с использованием математических/побитовых операторов? Алгоритм для всех значений тривиален с использованием условий или циклов, поэтому я не заинтересован в этом.
Дизайн алгоритма, как правило, является слабым местом для меня, поэтому я не знаю, действительно ли мой алгоритм "так же хорош, как он получается", только при использовании математических/побитовых операций. Благодаря
Ответы
Ответ 1
Я не думаю, что это так, что 1 < 32 обертывания (в противном случае, почему 2 < 31 также не обертывается?) вместо этого я считаю, что внутренний модуль 32 применяется ко второму оператору, поэтому что 1 < 32 фактически эквивалентно 1 < 0. Кроме того, рассмотрите возможность изменения типов параметров с "int" на "unsigned int". Чтобы получить значение "единиц" без использования проблемы "1 < 32", вы можете сделать это:
unsigned int ones = (0xffffffff >> (32-numbits)) << at;
Я не верю, что для этого типа существуют "стандартные" методы. Я уверен, что есть другие способы использования побитовых операторов по-разному для достижения одного и того же результата, но ваш алгоритм не хуже любого.
Сказав, что, однако, важна ремонтопригодность и документация. Ваша функция выиграет от того, что алгоритм документирован с комментарием, особенно для объяснения того, как вы используете побитовый XOR - который умный, но не простой для понимания на первый взгляд.
Ответ 2
Я не думаю, что это можно сделать более эффективным, если вы не написали ассемблер.
Вы можете улучшить читаемость и решить свою проблему переполнения, изменив некоторые мелочи:
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);
}
Более эффективная версия ассемблера (VС++):
// 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
}}
- 1-й aproach: медленнее на 32-битной архитектуре.
- 2nd aproach: (~ 0u) и (sizeof (int) * 8) вычисляются во время компиляции, поэтому они не берут никаких затрат.
- 3rd aproach: вы сохраняете 3 ops (обращения к памяти), записывая их на ассемблере, но вам нужно будет написать ifdefs, если вы хотите сделать его переносимым.
Ответ 3
Это довольно хорошо: я пробовал эту альтернативную версию, но ваш тест был примерно на 30% быстрее:
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);
}
Ответ 4
Обобщенная форма 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);
}
Ответ 5
Я думаю, что это вряд ли может быть более эффективным. Более того, побитовые операции намного быстрее, чем любые алгебраические операции.
Ответ 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 );}
Ответ 7
uint32_t
copy_bits (uint32_t dst, 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;
}
