алгоритм поиска подмножества большого массива int, который соответствует логическому запросу

Скажем, у меня есть большой массив из M 32-битных целых чисел, в котором каждое значение имеет не более N бит набор. Теперь я хочу вернуть подмножество, которое соответствует запросу Target AND Value == Target, т. Е. Значения, в которых биты целей появляются, установленные в значениях массива.

Грубая сила проста, просто выполните итерацию массива и извлеките, где target & value == цель. Это становится слишком медленным, если M становится очень большим. Кто-нибудь знает, как преобразовать массив в структуру данных, более оптимальную для поиска?

Один из способов - хранить массивы или значения для каждого бита (таким образом, для 32-битного массива вам нужно 32 из них), а затем только поиск значений, соответствующих каждому биту целевого значения. Это немного помогает, если N не приближается к 32 или у цели не установлено около N бит. Так как то, что я ищу, по сути, является частичным совпадением, хеширование или сортировка, похоже, не помогают.

Требуются точные правильные результаты. Это должно будет работать без доступа к параллельному оборудованию (например, графическому процессору или использованию SIMD).

Я буду использовать C ++, но достаточно лишь некоторых указателей на алгоритмы или идеи. Наиболее вероятным случаем будет M = 100000 и N = 8, и он будет вызываться часто.

Еще раз повторюсь: мне нужно частичное совпадение (например, item = 011000 match target = 001000), а не точное совпадение. Хотя элементы M известны заранее, возможные значения целей могут быть любыми.

В конце концов я решил использовать грубую силу. Для 80 000 предметов больше ничего делать не стоит. Я полагаю, если бы размер набора данных был больше 800000000, это могло бы того стоить.