用于从一个int到另一个int的任意位置复制N位的算法

2018-06-13 01:33:58

过去几天我一直在思考的一个有趣问题是如何将一个整数的位复制到目标整数给定位置处的另一个整数中。因此，例如，给定目标整数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 << 32导致1 （因为换档环绕）而不是0。

我的问题是：

这通常如何完成？有没有特别值得注意的算法（值得注意的是，我问是否有任何特别有效的技巧可以用来做到这一点）？

我的算法和我认为的一样好吗（也就是说，除了= 0和numbits = 32之外的所有值都适用）？

与1）相关，是否有任何方法只使用数学/位运算符来做到这一点？所有值的算法使用条件或循环是微不足道的，所以我对此不感兴趣。

算法设计对我来说通常是一个弱点，所以我不知道只使用数学/按位运算时，我的算法是否“尽可能好”。谢谢

我不认为1 << 32包装（否则，为什么不是2 << 31也包装？），而是我认为内部模数32应用于第二个运算符，所以1 << 32实际上相当于1 << 0。另外，考虑将参数类型从“int”更改为“unsigned int”。要获得“ones”的值而不会遇到“1 << 32”问题，可以这样做：

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

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

尽管如此，可维护性和文档也很重要。您的功能可以从记录了评论的算法中受益，特别是解释如何使用按位异或 - 这很聪明，但乍看起来不易理解。

除非您编写汇编程序，否则我认为不会更高效。

你可以提高可读性并解决你的溢出问题，改变一些小东西：

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。

它非常好：我尝试了这个替代版本，但你的测试速度快了大约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);
    }

链接地址: http://www.djcxy.com/p/37289.html

上一篇: Algorithm for copying N bits at arbitrary position from one int to another

下一篇: Expand a random range from 1–5 to 1–7