Найдите бит без дубликатов среди нескольких битов в Java
Я работаю над проектом в Java и использую биты для представления возможных чисел. Если дать каждому числу что-то вроде {2}, это будет 100 в двоичном формате, то есть 2^2, а {0,1,2} будет 111 в двоичном формате, то есть 2^2 + 2^1 + 2^0. Я пытаюсь выяснить, есть ли хоть один бит, который не повторяется в нескольких наборах. пример: из этих наборов {3,5,7}{3,5,9}{3,5,9}{1,5,6,9}{5,6,7,9}{3,7,9} Я хочу найти {1}, потому что это единственный файл без дубликатов.
На самом деле я пробовал аналогичную проблему в Python и также решил, что если есть способ сделать это с использованием наборов, то, вероятно, есть способ сделать это с использованием битов, но то, как я это сделал, было просто перебором. Технически вы можете просто и все комбинации (в моем случае 23) из 2 битов, затем или их, но я как бы надеялся на более быстрый метод с меньшим количеством циклов.
Ответы 1
Вы можете использовать две битовые маски: одну, отслеживающую, какие биты были просмотрены хотя бы один раз, и другую, отслеживающую, какие биты были просмотрены более одного раза.
int atLeastOnce = 0;
int moreThanOnce = 0;
for (int i = 0; i < sets.length; i++) {
moreThanOnce |= sets[i] & atLeastOnce;
atLeastOnce |= sets[i];
}
После этого atLeastOnce & ~moreThanOnce дает маску битов, которые были установлены ровно один раз. Вы можете определить, существует ли такой бит, просто сравнив его с нулем, и получить индекс самого младшего элемента, который встречается ровно один раз (если он есть), с помощью Integer.numberOfTrailingZeros.
Спасибо за поддержку, в моем первом посте все кажутся агрессивными. Я также новичок в манипуляциях с битами, и это кажется слишком необычным. Я виноват, что задал такой простой вопрос
@AlexanderLiu, возможно, это поможет: вы можете в основном думать об основных побитовых операциях как об операциях над множествами (& — пересечение, | — объединение, ^ — симметричная разность, a & ~b — «нормальная» разность множеств), и можете ли вы написать свой алгоритм в терминах этих «массовых операций» между наборами затем преобразуется в побитовый алгоритм, когда наборы представлены как наборы битов. Приведенный выше алгоритм также можно рассматривать таким образом: он создает набор элементов, видимых хотя бы один раз, и набор элементов, видимых более одного раза, причем «набор элементов, видимых ровно один раз» является их разницей.
Использование битов для представления набора может указывать только на наличие элемента. Если вы хотите указать присутствие и дубликат, вам понадобится более одного бита. Если вы хотите хранить наборы как биты, вам придется использовать битовые операции между наборами для определения дубликатов. В противном случае вы можете использовать коллекции Java — используйте
Mapс элементами набора в качестве ключа и целым числом в качестве значения.