从一个整数的任意位置复制 N 位到另一个整数的算法

Question

我最近思考了一个有趣的问题，如何在目标整数的给定位置将一个整数的位拷贝到另一个整数中。例如，给定目标整数 0xdeadbeef 和源整数 0xabcd，如果目标位置是16位，那么结果将为0xabcdbeef，如果目标位置是8位，则结果将为0xdeabcdef。

在避免使用条件语句或循环（只允许使用数学和位运算）的任意限制下，我开发了以下函数（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<<32的结果为1而不是0）外，此算法适用于所有值。

我的问题如下：

1. 通常如何完成这个任务？是否有任何特别显著的算法可以使用（通过“显着”，我是在问是否有任何特别高效的技巧可以用来完成这个任务）？
2. 我的算法是否与我认为的一样有效（也就是说，适用于除了at=0和numbits=32之外的所有值）？
3. 与1）相关，是否有办法只使用数学/位运算符来完成这个任务？对于所有值的算法使用条件或循环是微不足道的，因此我对此不感兴趣。

算法设计通常是我比较弱的地方，所以我不知道我的算法是否“尽善尽美”只使用数学/位运算符。谢谢

- GRB

---

这真是太棒了！我偶尔需要在每个周期都很重要的环境中操作大小奇怪的位字符串 - 我一定会把它加入我的技巧库。 - Jim Lewis

我应该提醒一下，我只进行了一些表面测试，所以不能保证这种方法百分之百有效。 - GRB

为避免符号位的任何问题，使用无符号整数可能更安全。 - Craig McQueen

Answer 1

除非您编写汇编语言，否则我认为无法更加高效地完成。

您可以通过改变一些小细节来提高可读性并解决溢出问题：

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

• 第一种方法：在32位架构上速度较慢。
• 第二种方法：(~0u)和(sizeof(int)*8)在编译时计算，因此它们不会产生任何费用。
• 第三种方法：使用汇编语言编写可以节省3个操作(内存访问)，但如果想要使其可移植，您需要编写ifdefs。

- Fernando N.

---

在32位架构下，这会带来性能损失。他没有要求代码美化工具或解决“溢出问题”，如果该函数仅用于numbits<32，则可能根本不存在该问题。他确实要求更快的版本。 - Gunther Piez

首先，你有没有读我的第一句话？第二，你在哪里看到这个函数只用于numbits<32？"numbits是从源复制的位数（1-32）"。第三，当你编写算法时，可读性是基本的，并且只是一个建议。在32位架构上确实会有一点性能损失，但与被接受的解决方案相反，它是可移植的。 - Fernando N.

@fnieto: sizeof(int)/sizeof(destination)/sizeof(source) 也可以工作，而且不需要 ACE 头文件。 - GRB

@GRB：你说得对，在这种情况下，我认为sizeof将始终在编译时评估。因此，我编辑以将ACE_SIZEOF_INT更改为sizeof（int）。无论如何，如果有人确认这不是编译器相关的，那就太好了。初步查看标准，我没有找到它。 - Fernando N.

5.19/1保证了sizeof是一个常量表达式（因此我认为这意味着它在编译时被评估，参见3.6.2/1）。 - GRB

是的，只有在C99中有一种情况（VLA），其中sizeof不会在编译时计算。请查看此处的litb答案：https://dev59.com/E3RB5IYBdhLWcg3wSVcI - Fernando N.

Answer 2

我认为1<<32不会溢出（否则，为什么2<<31不会溢出？），相反，我认为在第二个操作数上内部应用模32，因此1<<32实际上等同于1<<0。另外，考虑将参数类型从“int”更改为“unsigned int”。要获取“ones”的值而不遇到“1<<32”问题，您可以这样做：

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

我不相信有任何这种操作的“标准”方法。我确信还有其他使用位运算符以不同方式实现相同结果的方法，但你的算法和任何一种算法一样好。

话虽如此，可维护性和文档也很重要。您的函数将从算法被记录在注释中受益，尤其是解释如何使用按位异或 - 这很聪明，但乍一看不容易理解。

- Todd Owen

---

这将把一个 numbits == 0 的问题替换为一个 numbits == 32 的问题，但由于这样并没有太多意义，因此它可以被排除在函数允许的范围之外。 - caf

你说得对，“wrap”可能不是最合适的词。我本意是指那个执行内部模数运算的操作（正如你所提到的）。 - GRB

此解决方案依赖于架构。将0xffffffff替换为~0（无成本，编译时间），并将32替换为在您想要支持的架构中定义的宏INT_SIZE。 - Fernando N.

0确实很棒。这里有一个“ones”的计算方法，即使不使用INT_SIZE也可以实现可移植性：(~0 << numbits) << at; - Todd Owen

@ToddOwen：正式地说，将带符号的值向左或向右移动与位数相等是未定义的，许多情况下甚至不会进行移位操作，此时底层架构甚至都不相关。 - Mooing Duck

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

- RBarryYoung

---

那个表格用十六进制可能更有意义。 - Mooing Duck

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

- Sandeep Datta

Answer 5

复制位(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;

}

- Rao

---

如果您解释一下，您的答案会更有意义。 - devlin carnate

Answer 6

我认为它几乎不能更有效率。此外，按位运算比任何代数运算都要快得多。

- Havenard

---

我认为在这两点上你都是错误的。它可以更高效（请参见我的回答），而且在我所知道的每种架构中，加减法至少与按位操作执行速度相同。 - Gunther Piez

Answer 7

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

- Anr

---

已经测试过了，但是欢迎任何改进意见。有关是否将“大型”函数内联到末尾的建议呢？ - Anr

关于性能，我认为它与之前提出的相当。也许bits_cpy会更快一些，因为它只需要四个操作（除了掩码），而不是五个。 - Anr