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

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 << 32导致1(从转移包裹)而不是0.

我的问题是:

1. 这通常是怎么做的？是否有任何特别值得注意的算法使用(值得注意的是,我问是否有任何特别有效的技巧可以用来做到这一点)？
2. 我的算法是否能像我认为的那样工作(也就是说,除了= 0和numbits = 32之外,它适用于所有值)？
3. 与1)相关,有没有办法只使用数学/位运算符？所有值的算法使用条件或循环是微不足道的,所以我对此不感兴趣.

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

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个方法:你在汇编程序中保存3个操作(内存访问),但如果你想让它可移植,你需要编写ifdef.

Answer 2

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

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

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

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