[C/C++] перетасовка бит в целом числе

Вообсче то, компилятор сам не дурак и циклы разворачивает даже эффективней, чем тупую последовательность команд

Компилятор, компилятору рознь. Если бы, в свое время, компилятор в AVR-gcc «эффективно разворачивал», то ковыряться с ассемблером бы не пришлось. Сейчас, правда, не знаю, может получше стало.

> > Какая таргет платформа?

> x86_64

Какие ограничения на latency, bandwith?

А тот код, что предложили Вы, делает не то что нужно;-)

0b1111 -> 0b1001001001

В общем случае все, что можно сделать — распределить инструкции так, чтобы операнды следующей инструкции не зависели от результатов предыдущей, позволив соседним инструкциям выполняться параллельно.

А, да, и правда бес попутал.

Как насчет такого наблюдения: пусть i — номер бита в исходном слове, j — номер бита в результате. Затем мы начинаем побитовое преобразование исходного слова в результат по следующему алгоритму:

#define F ((uint64_t)-1) // слово нужной размерности, забитое единицами для формирования битовых масок
#define N 4              // количество бит в исходном числе
#define S 2              // число нулей, которые нужно вставить между битами исходного числа
uint64_t transform(uint64_t in)
{
    unsigned i;
    for (i = N - 1; i; i--) {
        unsigned j = i * (S + 1) + 1;
        uint64_t add = (F << i) & (F >> (64 - j + 1));
        uint64_t and = ~((F << i) & (F >> (64 - j + 1)));
        in = (in + add) & and;
    } while (i);
    return in;
}

Т. к. у тебя S известно заранее, составляем таблицу из значений add и and (с этим, думаю, справишься самостоятельно), а в варианте с кодогенератором — хардкодим эти значения в выводимый код. Итого две операции на бит (правда не параллелящихся), но зато сам алгоритм таков, что легко и непринужденно ложиться на sse — нужно только сложение и побитовое &. И, если меня не подводит память, эти операции есть на GPU, поэтому алгоритм легко и непринужденно распараллелится и между сотнями GPU'шных ядер.

я же говорю, фейковый. Хранить он будет только 64 бита, а прикидываться будет например 1Гб (для совместимости, чтоб комп запустился), читать и писать в них можно по любому адресу, выделенному для этого модуля

Чтение из рамы это около 1000 тактов, запись в первый кеш 4, в регистр 1. Ты уверен, что не особо быстрый алгоритм, который обрабатывает слово и оперирует регистрами будет «думать» дольше?

Алгоритм забавный, спасибо, но у меня уже есть алгоритм с тремя операциями на бит которые параллелятся;-) И да, на сотни ядер GPU в контексте данной задачи это парралелить странно.... ;-)

Какие ограничения на latency, bandwith?

Хороший вопрос... эти преобразования необходимы для доступа к данным числодробилки. Сама математика числодробилки занимает условно 10 тактов ядра на одно преобразование, при этом доступ к памяти и проч. выжимается досуха - соответственно преобразования не должны тормозить основную задачу;-)

Как раз по мат индукции здесь и ищется(доказывается) самый бстрый алгортм. Достаточно лишь присмотреться к условию, как задача значительно упрозщается. Первое. Из исходных данных нам известно что результат должен помещаться в 64 бита. С учетом того, что конечных битов 64, а промежуточная еденица данных занимает 3 бита (Bn 0 0) то очевидно что исходное число не может быть больше 21 одного бита длинной(64 mod 3), т.о. максимальное количество итераций 21. Второе. Очевидно, что конечный результат это сумма значащих битов в новом положении, где соблюдается строгая зависимость нового и старого положения: j = i*3+2 ( 11 -> 100100 ), откуда мы видим что результат будет вида: Σ (Bi)*(1<<(i*3+2) ) , где Bi - бит исходного числа, i ∈ [0;21]

Точнее даже так
Σ Bi<<(i*3+2)

Есть беззнаковое целое (64 бита) число. вида ... b3 b2 b1 b0 где bi - бит на соотв. позиции (в двоичной сист счисления). Нужно превратить его в ... b3 0 0 b2 0 0 b1 0 0 b0, те напихать между битами исходного числа некоторое кол-во нулей

Если ничего не напутал, то аналитическое решение такое:

#include <stdint.h>

#define IS_EVEN(N)                              \
    ((N) % 2 == 0)

#define IS_POWER_OF_TWO(N)                      \
    (((N) & ((N) - 1)) == 0)

static inline uint64_t power(uint64_t n, uint8_t k)
{
    uint64_t res = 1;

    for (; k > 0; k--)
        res *= n;

    return res;
}

uint64_t spread_bits(uint64_t n, uint8_t k)
{
    if (IS_EVEN(n))
        if (IS_POWER_OF_TWO(n))
            return power(n, k + 1);
        else
            return spread_bits(n / 2, k) * power(2, k + 1);
    else
        return spread_bits(n - 1, k) + 1;
}

но вообще напрашивается кодогенерация - из кода видно, что все нечётные выражаются через чётные, все чётные не степени двойки тоже рекурентно сводятся к произведению предыдущего результата и степени двойки, и только для степеней двойки нужно вычислять степень числа. Если k известно на этапе компиляции, то тут можно многое упростить. Ещё можно мемоизировать уже вычисленные значения.

антирекурсивный фикс:

uint64_t spread_bits(uint64_t n, uint8_t k)
{
    uint64_t add = 0, mul = 1;

    while (!IS_POWER_OF_TWO(n))
        if (IS_EVEN(n)) {
            n /= 2;
            mul *= power(2, k + 1);
        } else {
            n--;
            add += mul;
        }

    return add + mul * power(n, k + 1);    
}

у меня уже есть алгоритм с тремя операциями на бит которые параллелятся

Можно полюбопытствовать, какой? Если не коммерческая тайна, разумеется.

Прикольный код. Ты мерял его скорость?

Ещё можно мемоизировать уже вычисленные значения.

Просто песТня %)

На полке лежит два пирожка, Ваш посередине [C/C++] перетасовка бит в целом числе (комментарий)

[C/C++] перетасовка бит в целом числе (комментарий)

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

Не уверен, что компилятор способен эффективно соптимизировать Ваш хитрый while.

И главное - мое решение занимает две коротких строки и работает по крайней мере не медленней;-)

мой вариант короче на R-21 итераций и на 2 операции в каждом цикле.
Из этого можно сделать вывод, что никакие такты вы не щитаете.

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

Разумеется, можно сделать что-то вроде такого набора функций:

uint64_t intersperse_0_1(uint64_t n)
{
    uint64_t add = 0, mul = 1;

    while (!IS_POWER_OF_TWO(n)) {
        if (IS_EVEN(n)) {
            n /= 2;
            mul *= 2 << 1;
        } else {
            n--;
            add += mul;
        }
    }

    return add + mul * n * n;
}

uint64_t intersperse_0_2(uint64_t n);
uint64_t intersperse_0_3(uint64_t n);
// ...

Для чисел меньше 2^20 среднее количество итераций while будет равно десяти (количество последовательных делений чётных чисел на 2 и вычитания единицы из нечётных, чтобы получить из произвольного натурального числа степень двойки), так что общее количество выполняемых инструкций при вызове intersperse_0_* - примерно 100-200. Многовато, конечно.

Вот если найти способ вычислить для данного натурального числа нужную степень двойки вместе с add и mul не с помощью цикла а, опять же, арифметически, то можно сократить количество инструкций ещё больше.

С другой стороны, если делать через массив с забитыми значениями - исходя из этих соображений массив может быть в два раза меньше (только для чётных чисел), так как intersperse(2n + 1) = intersperse(2n) + 1.

Само рекуррентное условие такое:

intersperse(2^n)  = (2^n)^(k+1)
intersperse(2n)   = intersperse(n) * 2^(k+1)
intersperse(2n+1) = intersperse(2n) + 1

Возможно Вам здесь будет интересное для задачи: http://wasm.ru/forum/viewforum.php?id=17

Если бы между значащими битами было не 2, а 1или 3 нуля, то можно было бы составить хитрую константу, умножение на которую решало бы задачу.

Если бы между значащими битами было не 2, а 1или 3 нуля, то можно было бы составить хитрую константу, умножение на которую решало бы задачу.

101 / 11 = 5 / 3 != 21 / 7 = 10101 / 111.

В кольце по модулю 2^64 разве не может быть других делителей у 10101?

мой вариант короче на R-21 итераций и на 2 операции в каждом цикле.

Ваш вариант ПОЛНОСТЬЮ эквивалентен моему варианту по ссылке, только что у Вас вместо сдвига стоит зачем то умножение, а вместо or сложение (в данной задаче это одно и то же), кроме того у Вас цикл не до макс. знач бита (к-й известен), а до 21. Или у Вас число уже уже в виде массива бит представлено?

Из этого можно сделать вывод, что никакие такты вы не щитаете.

Я сразу решил, что Вы математик - Вы дали абс. точный и абс. бесполезный ответ, да еще на вопрос к-й я не задавал. И последний Ваш пост этот вывод подтверждает полностью, Вы мыслите настолько абстрактно, что даже такты посчитать не можете;-)

Если бы между значащими битами было не 2, а 1или 3 нуля, то можно было бы составить хитрую константу, умножение на которую решало бы задачу.

К сожалению нет. Одним умножением можно обойтись, только если в исходном числе битов меньше, чем вставляемых нулей.

В общем случае для втискивания произвольного числа бит в 64-битное слово получается что-то вроде:

x = (x & ~t[0]) | ((x & t[0]) << 32);
x = (x & ~t[1]) | ((x & t[1]) << 16);
x = (x & ~t[2]) | ((x & t[2]) << 8);
x = (x & ~t[3]) | ((x & t[3]) << 4);
x = (x & ~t[4]) | ((x & t[4]) << 2);
x = (x & ~t[5]) | ((x & t[5]) << 1);

x = (x | (x << 32)) & t[0];
x = (x | (x << 16)) & t[1];
x = (x | (x <<  8)) & t[2];
x = (x | (x <<  4)) & t[3];
x = (x | (x <<  2)) & t[4];
x = (x | (x <<  1)) & t[5];

Нераспарсил;-( t[] можно привести? Скажем для двух нулей.

Эх, я сейчас вдалеке от компиляторов. Но вот, например, тут приведены константы для двух нулей: http://stackoverflow.com/questions/1024754/how-to-compute-a-3d-morton-number-...

Это похоже то, что нужно, спасибо! Оно явно быстрее... правда я пока не могу понять как оно работает;-(

В кольце по модулю 2^64 разве не может быть других делителей у 10101?

Система

3k = 5 (mod 2^64)
7k = 21 (mod 2^64)

разве имеет решение? :)

Смысл в том, что любой сдвиг от 0 до 63 можно представить в виде x << (b6 * 32) << (b5 * 16) << (b4 * 8) << (b3 * 4) << (b2 * 2) << b1, где b6..b1 — это просто двоичные цифры (т.е. либо сдвигаем на константу, либо оставляем на месте) из сдвига, представленного в двоичном виде. А управлять сдвигом каждого конкретного бита (сдвигаем или не сдвигаем) можно при помощи битовых масок.

Да, я уже сообразил. Красиво...