Алгоритм для копирования N биты в произвольном положении от одного интервала до другого
Я думаю, что хорошие программы CS должны преподавать основные принципы, которые будут служить Вашей основой для всего будущего образования программирования. Методологии разработки как Гибкие инструменты, и управления версиями похожи на популярные товары; они приходят и уходят. Кроме того, они имеют тенденцию использоваться в промышленных настройках и не академических, таким образом, я думаю, что редко для университетов покрыть вещи, такие как те, которые Вы, вероятно, изучите на задании. Я не говорю, что это правильно, но это - вероятно, академический менталитет.
4 ответа
Я не думаю, что 1 << 32 обертывается (иначе, почему 2 << 31 не обертывается?), Вместо этого я думаю, что внутренний модуль 32 применяется к второй оператор, так что 1 << 32 фактически эквивалентно 1 << 0. Также рассмотрите возможность изменения типов параметров с «int» на «unsigned int». Чтобы получить значение «единиц», не сталкиваясь с проблемой «1 << 32», вы можете сделать следующее:
unsigned int ones = (0xffffffff >> (32-numbits)) << at;
Я не верю, что существуют какие-либо «стандартные» методы для такого рода операций. Я уверен, что есть и другие способы использования побитовых операторов по-разному для достижения того же результата, но ваш алгоритм ничуть не хуже других.
Однако, при этом важны также удобство обслуживания и документация.
Достаточно хорошо: я пробовал эту альтернативную версию, но ваша тестировалась примерно на 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);
}
Я не думаю, что это можно сделать более эффективно, если вы не пишете ассемблер.
Вы можете улучшить читаемость и решить проблему переполнения, изменив некоторые мелочи:
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
}}
- 1-й подход: Медленнее на 32-битной архитектуре
- 2-й подход: (~ 0u) и (sizeof ( int) * 8) вычисляются во время компиляции, поэтому они не требуют никаких затрат.
- 3-й подход:Вы экономите 3 операции (доступ к памяти) , записывая его на ассемблере, но вам нужно будет написать ifdefs, если вы хотите сделать его переносимым.
Думаю, это вряд ли может быть эффективнее. Более того, поразрядные операции намного быстрее, чем любые алгебраические операции.