代码之家 › 专栏 › 技术社区 › GRB

任意位置n位从一个int复制到另一个int的算法

bit-manipulation algorithm c++

GRB · 技术社区 · 15 年前

过去几天我一直在思考的一个有趣的问题是如何将一个整数的位复制到目标整数中给定位置的另一个整数中。例如,给定目标整数 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)。据我所知,该算法适用于除 在 = 0和 数字 =32(当源整数覆盖整个目标整数时的情况),因为1<<32导致1(因为移位环绕),而不是0。

我的问题是:

这通常是怎么做到的?有没有特别值得注意的算法被使用(值得注意的是,我在问是否有任何特别有效的技巧可以用来做这件事)?
我的算法和我想的一样有效吗(也就是说,除了at=0和numbits=32之外,所有值都有效)?
关于1),是否只有使用数学/位运算符才能做到这一点?使用条件或循环,所有值的算法都很简单,所以我对此不感兴趣。

算法设计对我来说通常是一个弱点,所以当我只使用数学/位运算时,我不知道我的算法是否“达到它所能达到的水平”。谢谢

7 回复 | 直到 8 年前

Todd Owen 15 年前

我不认为是1<<32包装的情况(否则,为什么2<<31也不包装?)相反,我认为内部模32应用于第二个运算符,因此1<<32实际上等于1<<0。另外,考虑将参数类型从“int”更改为“unsigned int”。要在不遇到“1<<32”问题的情况下获得“一”的值,可以执行以下操作:

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

我不相信这种操作有任何“标准”方法。我确信还有其他方法可以用不同的方式使用位运算符来获得相同的结果,但是您的算法和其他算法一样好。

尽管如此,可维护性和文档也很重要。您的函数将受益于用注释记录的算法,特别是解释如何使用位异或——这很聪明,但一眼就不容易理解。

Fernando N. 15 年前

我认为如果不编写汇编程序,就不能提高效率。

您可以提高可读性并解决溢出问题,更改一些小东西:

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。

RBarryYoung 15 年前

很好:我试过这个替代版本,但你的测试速度快了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);
    }

Sandeep Datta 14 年前

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

Havenard 15 年前

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

Anr 10 年前

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

Rao 8 年前

UIT32 复制_位(uint32_t dst、uint32_t src、uint8_t end_位、uint8_t start_位)

{

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;

}