Эффективное смещение двоичной строки в C ++ - PullRequest
Новая
       7

Эффективное смещение двоичной строки в C ++

0 голосов
/ 10 ноября 2018

Если у меня есть строка, представляющая целое число в двоичной форме, например 

1101101

и я хочу повернуть вправо, чтобы получить 

1110110

Один из способов, которым я мог бы придумать, это преобразовать строку в int и использовать (взято из wikipedia ) 

// https://stackoverflow.com/a/776550/3770260
template <typename INT>
#if __cplusplus > 201100L // Apply constexpr to C++ 11 to ease optimization
constexpr
#endif // See also https://stackoverflow.com/a/7269693/3770260
INT rol(INT val, size_t len) {
#if __cplusplus > 201100L && _wp_force_unsigned_rotate // Apply unsigned check C++ 11 to make sense
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
#endif
    return (val << len) | ((unsigned) val >> (-len & (sizeof(INT) * CHAR_BIT - 1)));
}

Однако, если строка состоит, скажем, из 10 ^ 6 char, это не сработает, так как целочисленное представление превышает даже диапазон __int64.

В этом случае я мог бы придумать решение, перебрав строку 

//let str be a char string of length n
char temp = str[n - 1];
for(int i = n - 1; i > 0; i--)
{
    str[i] = str[i - 1];
}
str[0] = temp;

Это решение работает в O(n) из-за цикла по длине строки, n. У меня вопрос, есть ли гораздо более эффективный способ реализации циклического сдвига для больших двоичных строк?

EDIT

Вход и выход std::string с

1 Ответ

0 голосов
/ 10 ноября 2018

Вам нужно переместить память тем или иным образом, поэтому предлагаемое вами решение будет настолько быстрым, насколько это возможно.

Вы также можете использовать стандартные функции std::string: 

str.insert(str.begin(), str[n - 1]);
str.erase(str.end() - 1);

или memmove, или memcpy (я на самом деле не рекомендую это, это для аргумента) 

char temp = str[n - 1];
memmove(str.data() + 1, str.data(), n - 1);
str[0] = temp;

Обратите внимание, что memmove может выглядеть быстрее, но по сути это то же самое, что и ваш цикл. Он перемещает байты один за другим, он просто заключен в другую функцию. Этот метод может быть быстрее для гораздо больших блоков данных размером 1000 байт или более, поскольку ЦП оптимизирован для перемещения больших кусков памяти. Но вы не сможете измерить разницу для 10 или 20 байтов.

Более того, компилятор, скорее всего, запустит дополнительные оптимизации, когда увидит ваш цикл for, обнаружит, что вы перемещаете память, и выберет лучший вариант.

Компилятор также хорош в работе с std::string методами. Это обычные операции, и компилятор знает, как лучше всего их обработать.

...