Как замаскировать целые числа с помощью побитовых операторов

Мне было интересно, есть ли способ замаскировать список значений int с помощью побитовых операторов и использовать эту маску, чтобы узнать, является ли значение int одним из значений, которые находятся в маске.

то есть, если у меня есть значения 129 и 17, как я могу рассчитать маску, которая сообщает мне, соответствует ли значение int в маске (если значение int равно 129 или 17).

Я ожидаю, что моя проблема будет лучше понята со следующим псевдокодом.

**EDIT: я хочу упаковать, замаскировать или «сжать» массив int только в одно значение (маску), а затем принять только те значения, которые находятся в списке значений для маскирования (массив).

Является ли это возможным? Заранее спасибо.

valuesToMask = [17, 129, ...]
mask = getmask(valuesToMask)
lstValues = [0,1, 10, ..., 17, 18, 19, ..., 129, ...]
foreach(int value, in lstValues) {
    if(check(mask,value)) 
       printf("\nValue %d is in the mask", value);
    else 
       printf("\nValue %d is not in the mask", value);
}

Заранее спасибо. Я очень ценю вашу помощь и ваше время.

(Извините за мой английский)


bloom-filter bit-manipulation bitmask bitwise-operators
person Hermandroid    schedule 03.05.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Вы можете сделать это для определенных наборов значений, но не обязательно в целом. Например, если вы хотите определить, равно ли значение 4, 5, 6 или 7, вы можете сделать:

if ((value & ~3) == 4) ...

Это создает маску со всеми битами 1, кроме двух младших битов. Оператор & эффективно устанавливает младшие два бита в 0. Затем сравнение проверяет, соответствует ли шаблон битов искомому значению. В двоичном представлении это выглядит следующим образом (предположим, что value является 8-битным значением):

value        masked
00000011     00000000 = 0
00000100     00000100 = 4
00000101     00000100 = 4
00000110     00000100 = 4
00000111     00000100 = 4
00001000     00001000 = 8

Этот метод не будет работать, если, например, вы хотите проверить только «4, 5 или 7».

person Greg Hewgill    schedule 03.05.2012
comment
Таким образом, значения для проверки с использованием этого метода должны быть продолжены? - person Hermandroid; 04.05.2012
comment
Нет, это был просто пример, который я использовал. Например, вы можете проверить наличие четных чисел между 8 и 14, используя (value & ~6) == 8. - person Greg Hewgill; 04.05.2012

arrow_upward
2
arrow_downward

Вы можете частично решить проблему с помощью фильтров Bloom. Это работает так: чтобы проверить принадлежность к N-набору элементов, вы определяете K хеш-функции для сопоставления каждого элемента с M-битным ключом. Для вставки элемента a установите биты фильтра в позициях h1(a) ... hk(a) равными 1. Для поиска элемента b, если вы обнаружите нулевой бит в любой из h1(b) ... hk(b), то b гарантированно не быть в комплекте. Однако в зависимости от значений N, M и K существует небольшая вероятность того, что вы получите ложное срабатывание (т. е. вы не обнаружите нулей в хеш-функциях, но b ранее не сохранялось в фильтре).

В псевдокоде:

const int M = 256;
typedef std::bitset<M> Mask;

int listValues[N] = { v1, ... , vN };
typedef unsigned char (*)(int) HashFunction; // maps int to 0...255
HashFunction hash[K] = { h1, ..., hK };

Mask make_mask(int x)
{
    Mask m(0):
    for (int i = 0; i < K; ++i) { 
        m[(hash[i])(x)] = 1; // update mask with item's hash
    }
    return(m);
}    

// initialize
Mask BloomFilter(0);
for (int i = 0; i < N; ++i) {        
    BloomFilter |= make_mask(listValues[i]);
}

// probe
bool is_not_in_filter(const Mask& F, int x)
{
    // if a zero-bit in F matches a 1-bit in make_mask(x), then x is not in F
    return ~F & make_mask(x) != 0; 
}

// call
int x = ...;
bool in_set = is_not_in_filter(BloomFilter, x);

По сути, это расширяет каждый элемент до M-битного ключа, а фильтр представляет собой агрегированное побитовое ИЛИ по всем элементам. Затем тестирование на принадлежность к набору становится простым (хотя и вероятностным) побитовым И между ОТРИЦАТЕЛЬНЫМ фильтром и М-битным расширенным элементом, подлежащим тестированию.

ОБНОВЛЕНИЕ: приведенный выше код представляет собой псевдокод, объясняющий, как он работает. Чтобы получить актуальную библиотеку, см., например. экспериментальные Boost.Bloomfilters или цветок

person TemplateRex    schedule 04.05.2012
comment
вау, я этого не знал, я очень ценю вашу помощь, я проверю, как это работает. Спасибо - person Hermandroid; 05.05.2012
comment
@Herman смотрите обновленный ответ для ссылок на актуальные библиотеки. - person TemplateRex; 05.05.2012

arrow_upward
-1
arrow_downward

Я думаю, вы спрашиваете, как вы можете проверить, является ли число 129 или 17.

int[] lstValues = [0,1, 10, 17, 18, 19, 129];
foreach(int value in lstValues) {
    if(lstValues == 129 || lstValues == 17) 
        printf("\nValue is in the mask");
    else 
        printf("\nValue is not in the mask");
}
person m12    schedule 03.05.2012
comment
да, это идея, но мне нужно оставить 129 и 17 как единственное значение - person Hermandroid; 04.05.2012