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).
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);
}
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.
My questions are:
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
I don't think it can be done more efficient unless you write assembler.
You can improve the readability and solve your overflow problem changing some little things:
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);
}
More efficient assembler version (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
}}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With