Логический оператор И с условием

Question

Учитывая пороговое значение T и набор растровых изображений, я хочу создать результирующее растровое изображение «br», так что i-й бит «br» установлен в 1, только если i ' й бит устанавливается в 1 в> = T растровых изображениях.

Я попытаюсь проиллюстрировать мой вопрос на примере: Предположим, что мы имеем 4 растровых изображений (равностепенной длины) и T = 3:

b1 (10000) 
b2 (01110) 
b3 (10110) 
b4 (00010) 

Тогда мой полученный растровый ш = (00010) - потому что только 4-й бит установлен в 1 в> = 3 растровых изображениях. Если T = 2, то br = (10110).

Одним из наивных способов сделать это было бы перебрать каждый битмап и сохранить вектор, в котором хранится счет бит i в индексе i'th. После этого можно прокручивать этот вектор «счет».

Другим способом (я думаю) было бы реализовать модифицированный логический оператор И таким образом, чтобы в результирующем растровом изображении i-й бит был установлен в 1, если он установлен в 1 в положениях> = Т.

Есть ли другой эффективный способ сделать это? Я использую C++ и EWAHBoolArray (https://github.com/lemire/EWAHBoolArray). В настоящее время у них нет возможности выполнять операцию И между несколькими растровыми изображениями. Любой ответ очень ценится!

Answer 1

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

b1a = b1 & 0b01001; 
b1b = (b1 >> 1) & 0b01001; 
b1c = (b1 >> 2) & 0b01001; 
b2a = b2 & 0b01001; 
... 
bra = ((b1a + b2a + b3a + b4a + 0b01001) & 0b100100) >> 2; 
brb = ((b1b + b2b + b3b + b4b + 0b01001) & 0b100100) >> 1; 
brc = ((b1c + b2c + b3c + b4c + 0b01001) & 0b100100); 
br = bra | brb | brc;