Массив из 10000 с 16-битными элементами, набор битов поиска (неограниченное ОЗУ) - интервью Google

Об этом недавно спросили в моем интервью Google, и я предложил ответ, который включал битовый сдвиг и был O (n), но она сказала, что это не самый быстрый способ сделать это. Это. Я не понимаю, есть ли способ подсчитать набор битов без перебора всех предоставленных битов?