從一個int到另一個int的任意位置複製N位的算法

Question

過去幾天我一直在思考的一個有趣問題是如何將一個整數位複製到目標整數給定位置處的另一個整數。因此，舉例來說，給定目標整數0xdeadbeef和源整數0xabcd，該想法將得到0xabcdbeef（給定目標位置16位）或0xdeabcdef（給定目標位置8位）的結果。

以避免條件句或環中的任意的限制（允許自己使用只是數學/位操作），我開發下面的函數（C++）

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導致1 （因爲移回繞到），而不是0

我的問題是：

1. 這是如何正常進行？有沒有特別值得注意的算法（值得注意的是，我問是否有任何特別有效的技巧可以用來做到這一點）？
2. 我的算法和我認爲的一樣嗎（也就是說，除了= 0和numbits = 32之外的所有值都適用）？
3. 與1）相關，是否有任何方法只使用數學/位運算符來做到這一點？所有值的算法使用條件或循環是微不足道的，所以我對此不感興趣。

算法設計對我來說通常是一個弱點，所以我不知道我的算法在使用數學/按位運算時是否「像它得到的一樣好」。謝謝

Answer 1

我不認爲它的情況下1個< < 32包裝（否則，爲什麼沒有按't 2 < < 31也包裝？），而是我認爲內部模數32應用於第二個運算符，因此實際上等於1 < < 0另外，請考慮將參數類型從「int 「到」unsigned int「。要獲得「個位」的值，而不跑步進入「1 < < 32」的問題，你可以這樣做：

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

我不相信有對於這種操作的任何「標準」的方法。我確信還有其他方法可以以不同的方式使用按位運算符來實現相同的結果，但是您的算法與任何方法一樣好。

儘管如此，可維護性和文檔也很重要。您的功能可以從記錄了評論的算法中受益，特別是解釋如何使用按位異或 - 這很聰明，但乍看起來不易理解。

Answer 2

我認爲它幾乎不會更有效率。而且，按位運算比任何代數運算要快得多。

Answer 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); 
    } 

Answer 4

我不認爲它可以做得更有效率，除非你編寫彙編器。

可以提高程序的可讀性和解決您的溢出問題改變一些小東西：在32位架構較慢：

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); 
} 

更高效的彙編版本（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 
}} 

• 1日的aproach
• 第二個問題：（〜0u）和（sizeof（int）* 8）在編譯時計算，所以它們不收取任何費用。
• 第3個問題：你節省了3個操作數（內存訪問）把它寫在彙編程序中，但是如果你想使它變得可移植，你將需要編寫ifdefs。

Answer 5

廣義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（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; 

}