算法从一个INT复制N位在任意位置到另一个位置 [英] Algorithm for copying N bits at arbitrary position from one int to another
问题描述
这是有趣的问题，我一直在琢磨这几天是怎么一个整数的位复制到另一个整数在目的地整数一个给定的位置。因此，举例来说，给出的目标整数 0xdeadbeef 和源整数为0xABCD ，这个想法是将得到的结果对 0xabcdbeef （给定的16位的目标位置）或者 0xdeabcdef （给8位的目标位置）。
An interesting problem I've been pondering the past few days is how to copy one integer's bits into another integer at a given position in the destination integer. So, for example, given the destination integer 0xdeadbeef and the source integer 0xabcd, the idea would be to get a result of 0xabcdbeef (given a destination position of 16 bits) or 0xdeabcdef (given a destination position of 8 bits).
通过避免条件语句或循环的任意限制（允许自己只使用数学/位运算），我制定了以下功能（C ++）
With the arbitrary limitation of avoiding conditionals or loops (allowing myself to use just mathematical/bitwise operations), I developed the following function (C++)
int setbits(int destination, int source, int at, int numbits)
{
int ones = ((1<<(numbits))-1)<<at;
return (ones|destination)^((~source<<at)&ones);
}
其中，在是源位应该被复制到目标号码（0-31）的地方， NUMBITS 是位的数量从源（1-32）被复制。据我所知，这种算法适用于所有值，除了在 = 0和 NUMBITS = 32（当整个目的地整数被覆盖由源整数的情况），由于这样的事实，1所述;＆γ-32结果在1（由于移位回绕），而不是0。
where at is the place where the source bits should be copied into the destination number (0-31) and numbits is the number of bits being copied from source (1-32). As far as I can tell, this algorithm works for all values except for at = 0 and numbits = 32 (the case when the entire destination integer is being overwritten by the source integer) due to the fact that 1<<32 results in 1 (since the shift wraps around) as opposed to 0.
我的问题是：
- 这是怎么正常完成？有没有使用（由显着的，我问，如果有，可以用来做什么特别有效的招数）？什么特别显着的算法
- 请问我的算法工作，以及我认为它（即，适用于除了在= 0，所有值NUMBITS = 32）？
- 相关：1），有没有办法只有用数学/位运算符来做到这一点？该算法对所有的值是微不足道的使用条件或循环，所以我不感兴趣。
算法设计通常是一个薄弱点，我，所以我不知道我的算法是否仅仅时使用的数学/位运算，因为它得到一样好。谢谢
Algorithm design is usually a weak point for me, so I have no idea whether or not my algorithm is 'as good as it gets' when only using mathematical/bitwise operations. Thanks
推荐答案
我不认为它的情况下1＆LT;＆LT; 32包装（否则，为什么不2';＆LT; 31还包），而不是我认为，在内部模量32施加到第二操作者，从而使1所述;＆γ-32实际上相当于1所述;℃下。另外，还要考虑从INT到无符号整型改变参数类型。要获得1的值，而不运行到了1＆LT;＆LT; 32的问题，你可以这样做：
I don't think it's the case that 1<<32 wraps (otherwise, why doesn't 2<<31 also wrap?), instead I think that internally modulus 32 is applied to the second operator, so that 1<<32 is actually equivalent to 1<<0. Also, consider changing the parameters types from "int" to "unsigned int". To get the value of "ones" without running into the "1<<32" problem, you can do this:
unsigned int ones = (0xffffffff >> (32-numbits)) << at;
我不相信有任何标准的方法，这种操作。我敢肯定有使用位运算符以不同的方式来达到同样的结果的其他方法，但是你的算法是不比任何人差。
I don't believe there are any "standard" methods for this kind of operation. I'm sure there are other ways of using bitwise operators in different ways to achieve the same outcome, but your algorithm is as good as any.
话虽如此，不过，可维护性和文档也很重要。你的函数将受益于算法被证明与评论，尤其是讲解如何使用按位异或 - 这是聪明的，但不容易理解乍看
Having said that, though, maintainability and documentation is also important. Your function would benefit from the algorithm being documented with a comment, especially to explain how you use the bitwise XOR -- which is clever, but not easy to understand at first glance.
这篇关于算法从一个INT复制N位在任意位置到另一个位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
