2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вложимость бинарного представления целых
Сообщение07.11.2016, 15:07 
Проблему проще пояснить на примере :

Даны числа "кирпичики" 0-15 ( ниже 2а из них в бинарной записи )

0001
1011

Дано некое очень большое число состоящее из единиц ( те вида 2^n - 1 ).
Например 2^32-1 = 11111111111111111111111111111111

Для кирпичиков разрешена операция сдвига и сложения если ни одна из единиц не пересекается.
Вопрос : Какие из чисел кирпичиков после применения операций будут наиболее похожи на данное число.
А точнее как определить, тестовый "кирпичик" образует сдвигами последовательность единиц или нет?

Например берем 0001, сдвигами и оп ИЛИ можно получить 00011, 000111 и тд. до 0001..1. Следовательно кирпичик похож ( краевые эффекты не в счет ).

Теперь возьмем 1011, сдвигами можем получить 101110111011, и тд. Следовательно кирпичик не похож (есть 0и).

Приведенные числа маленькие и их тестировать просто, но если числа из десятков разрядов, то это становиться проблемой. Способ который сейчас используется это перебор сдвигов и рекурсивное вкладывание с проверкой на конфликты.

 
 
 
 Re: Вложимость бинарного представления целых
Сообщение07.11.2016, 15:14 
Аватара пользователя
Т.е. вопрос в том, можно ли из данного числа получить битовыми сдвигами влево и битовым или (которое можно применять только к числам, которые побитовое и которых нулевое) получить данное число? Непонятно, зачем тут нужен перебор.

 
 
 
 Re: Вложимость бинарного представления целых
Сообщение07.11.2016, 15:19 
Вообще вы наверное правы, достаточно сдвигов

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group