Ищу способ добавить два BitSet. Следует ли мне перейти к основам двоичного числа и выполнить операции XOR и AND над BitSet. Как сказано здесь: 
Будет ли это эффективно?
Как добавить два BitSet
Ответы (2)
Нет, это не будет эффективно, потому что вы не узнаете перенос для бита N, пока не обработаете все биты через N-1. Эта проблема решается с помощью аппаратных сумматоров с упреждающим просмотром.
Невозможно реализовать добавление BitSet таким образом, чтобы в худшем случае не проверялись все их биты один за другим. Альтернативная стратегия во многом зависит от ваших конкретных требований: если вы сильно изменяете свои битовые наборы, вы можете захотеть откатить свои собственные, основанные на реализации Oracle Sun. Вы можете бесстыдно скопировать заимствовать их код и добавить реализацию add, которая работает на «внутренностях» BitSet, хранящегося как long[] bits. Вам нужно быть очень осторожным при переполнении (помните, что все числа в Java подписаны), но в остальном это должно быть довольно просто.
person
Sergey Kalinichenko
schedule
30.03.2012
вы смешиваете действенное и действенное. Вы имеете в виду действительно эффективный (он работает правильно), когда вы говорите эффективный (он работает быстро / с меньшими ресурсами)
- person stefan bachert; 30.03.2012
@stefanbachert Я действительно имею в виду эффективность, потому что работает быстро. Вы можете использовать схему из OP в качестве основы для правильной реализации, но это потребует многократного объединения флагов переноса из полуадресов с результатами добавлений, пока у вас не будет новых флагов переноса; в худшем случае это может занять
N, где N - количество бит в большем из двух чисел.
- person Sergey Kalinichenko; 30.03.2012
Дай мне попробовать. если я могу управлять переносом, то это было бы лучше всего, иначе мне придется преобразовать его в целое / длинное.
- person Ravi Joshi; 30.03.2012
@RaviJoshi Вам не нужно пробовать это в коде, просто подумайте: мысленно установите все биты от 0 до 1000 в одном
BitSet, а в другом BitSet. Теперь сложите их вместе. Вы получите перенос в первом бите, ноль в нулевом бите и от единиц до 1000 в оставшихся битах. Теперь примените перенос и получите ноль в битах ноль и один, перенос во втором бите и полностью до 1000. Понятно, что вам нужно будет повторить это 1000 раз, чтобы добраться до конца, что грубо неэффективно.
- person Sergey Kalinichenko; 30.03.2012
@RaviJoshi (я не верю, что говорю это), вы можете использовать отражение, чтобы выудить массив
bits из BitSet (о нет, я сказал это!) Это сертифицированный хакер, так что делайте это на свой страх и риск. Мне нужно было сделать это один раз, чтобы сериализовать множество больших BitSet в достаточно успешном коммерческом продукте, и это сработало; однако я написал множество модульных тестов вокруг него и запускал их каждый раз, когда мы переходили на новую версию Java. Это ужасно, ужасно, поэтому не делайте этого без крайней необходимости.
- person Sergey Kalinichenko; 30.03.2012
@dasblinkenlight: у меня нет знаний об использовании отражения в java. Однако в настоящее время я думаю преобразовать оба битовых набора в целое число / долгое время, а затем выполнить сложение. это будет достаточно быстро? Если нет, то вы можете подробнее развить свою концепцию.
- person Ravi Joshi; 30.03.2012
@RaviJoshi Это преобразование происходит по одному биту за раз, поэтому оно довольно медленное. Если у вас все в порядке с его использованием, вы также можете добавлять по крупицам: это будет так же медленно.
- person Sergey Kalinichenko; 30.03.2012
@RaviJoshi Вы пробовали загрузить исходники для
BitSet с здесь, например, изменить имя пакета на имя вашей компании и скомпилировать его как свое собственное? Это должно быть очень просто, это автономный фрагмент кода. Это позволит вам полностью пропустить преобразование, что сэкономит огромное количество времени.
- person Sergey Kalinichenko; 30.03.2012
@dasblinkenlight: у меня уже есть полный исходный код JDK1.6, но где дополнительный код
BitSet? В настоящее время я использую BigInteger, чтобы добавить два BitSet большого размера. Сначала я конвертирую Bitset в StringBuilder следующим образом: `a - это BitSet StringBuilder sb1 = new StringBuilder (n); for (int j = 0; j ‹n; j ++) {int bit = a.get (n - j - 1)? 1: 0; sb1 = sb1.append (бит); } // sb2 определяется таким же образом для BitSet b BigInteger c = new BigInteger (sb1.toString (), 2) .add (new BigInteger (sb2.toString (), 2)); `Слишком медленно. :(
- person Ravi Joshi; 31.03.2012
@RaviJoshi Вам нужно написать этот дополнительный код самостоятельно. Используйте массив
bits BitSet так же, как setAdd метод of BigInteger использует свой массив под названием words. Обратите внимание, что массив BigInteger равен int, а не long, поэтому им легче справиться с переполнением. Ваша логика была бы несколько более сложной, но это выполнимо.
- person Sergey Kalinichenko; 31.03.2012
Самый эффективный способ - преобразовать оба битовых набора в числа и просто добавить их
person
stefan bachert
schedule
30.03.2012
Как развернуть
BitSet в неотрицательный BigInteger?
- person Mike Samuel; 30.03.2012
да, однако, я бы использовал int или long, когда биты ограничены этим
- person stefan bachert; 30.03.2012
@stefanbachert: Что, если этот
bitset большой? как использовать BigInteger в этом случае?
- person Ravi Joshi; 30.03.2012
это очень теоретически. В конце концов, речь идет о сложении двух чисел. Длинное число имеет 63-битный плюс. Long может считать с момента большого взрыва с шагом 2 нс. Все, о чем мы говорим, далеко от реального практического использования.
- person stefan bachert; 30.03.2012
bitsetклассом - person Ravi Joshi schedule 30.03.2012