Существует ли не итеративный метод включения и выключения групп битов с помощью маски? - PullRequest
Новая
       4

Существует ли не итеративный метод включения и выключения групп битов с помощью маски?

0 голосов
/ 31 марта 2020

Предположим, у меня есть две строки битов: runs и toggler, где цикл представляет собой группу смежных битов. Обе эти строки битов могут иметь произвольное расположение 1 и 0 (соответственно, включено и выключено). Ради этого вопроса я буду использовать приведенные ниже примеры значений: 

runs   : 1111011010100011
toggler: 1010001010010110

Существует ли способ маскирования двухбитных строк или иным образом использование каких-либо функций c ++ вне итерации (хотя более общее / независимое от языка, тем лучше), чтобы создать result битовую строку, которая содержит каждый прогон 1 с в runs, который имеет хотя бы один бит с соответствующим 1 в toggler? Работающий пример этого с использованием предоставленных примеров значений можно увидеть следующим образом: 

runs   : 1111011010100011
toggler: 1010001010010110
result : 1111011010000011

Где первый, второй, третий и четвертый прогоны 1 с в runs имеют по крайней мере один 1, соответствующий их составляющие биты в toggler.

До сих пор у меня есть очевидное, что позиции некоторых из result могут быть идентифицированы, будучи битами, соответствующими ~runs. Также очевидно, что позиции некоторых из result 1 могут быть идентифицированы как runs & toggler. Учитывая эту информацию, любые оставшиеся неизвестные биты (эквивалентные битам, которые удовлетворяют условию runs & ~toggler), могут быть определены как равные 0, если биты на обоих концах этого цикла неизвестных битов равны нулю. Это еще раз можно увидеть ниже в битовой строке unknown: 

runs   : 1111011010100011
toggler: 1010001010010110
unknown: 1_1_0_1010_0001_ // 1 = runs & toggler, 0 = ~runs, _(unknown) = runs & ~toggler
result : 1111011010000011

1 Ответ

1 голос
/ 31 марта 2020

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

Сначала приятная часть. Получение для каждой «группы» бита, указывающего, был ли включен какой-либо переключатель для этой группы. Подход может быть следующим: взять переключатели, вставить «блокировщик» 1 в бит сразу после группы и вычесть начальную точку каждой группы. Затем, если в группе не было установлено ни одного переключателя, «блокировщик» сбрасывается заимствованием. В противном случае, если есть набор переключателей, этот бит переключателя «съедает» заем, и блокировщик выживает. В коде: 

runs_first = runs & ~(runs << 1);
runs_after = ~runs & (runs << 1);
toggles_blocked = toggles | runs_after;
selected_groups = runs_after & (toggles_blocked - runs_first);

Пример с вашими номерами (с префиксом ноль, чтобы избежать неудачного крайнего случая): 

runs           : 01111011010100011
toggles        : 01010001010010110
runs_first     : 00001001010100001
runs_after     : 10000100101000100
toggles_blocked: 11010101111010110
difference     : 11001100100110101
selected_groups: 10000100100000100

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

rev_selected = reverse(selected_groups >> 1);
rev_runs = reverse(runs);
rev_runs_after = ~rev_runs & (rev_runs << 1);
rev_groupmask = (rev_runs_after - rev_selected) & rev_runs;
groupmask = reverse(rev_groupmask)

Но даже «эффективный реверс» не настолько эффективен, если для него нет прямой аппаратной поддержки (например, rbit на ARM, grevi на RIS C -V с расширением B).

...