Developing.ru

Помогите пожалуйста, нужно написать программу/
Найти все простые числа из заданной последовательности чисел, не превосходящие заданное натуральное число n, двоичная запись которых представляет собой симметричную последовательность нулей и единиц (начинающуюся единицей).
Цифры не должны заноситься в массив.

Ну более простого способа, чем следующий, я не придумал. Запустить два счётчика: от последнего бита и от первого, двигать счётчики друг на встречу другу и проверять равны ли биты, на которые счётчики указывают. Ну и делать это нужно для каждого числа от 1 до n в цикле.

Если отважишься запрограммировать самостоятельно, я могу расписать чуть детальнее алгритм.

Тут еще с симметрией непределенность получается. Например, 101 - вроде как симметрична, а 00000101 - уже нет, не смотря на то, что это одно и тоже число

Нет, в задании написано "начинающуюся единицей". Лидирующие нули мы должны опускать. То есть первый шаг - это найти левую границу откуда начинать сравнивать зеркальность. У меня есть стойкое предчуствие что первый ненулевой бит нашего числа x будет равен "целая часть от log_2 (x)". Всё верно?

Ну да. На ассемблере я бы сделал так:
Если принять N = log_2 (x), то я бы крутил бы Х вправо, а другое число У , первоначально равное 0 - крутил бы влево через флаг переноса. Через N итераций в Y было бы перевернутое число. В случае зеркального расположения битов Х = У в конце.
На сях вращение - это
У = (Y << 1) + (Х & 1); (синтаксис плохо помню)

На ассемблемере там основной цикл вообще в десяток команд укладывается. Но, к сожалению, в С++ у нас напрямую не доступен флаг переноса и команды sbb и adc, учитавающие этот регистр.

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

Использую всё тот же интуитивно понятный алгоритмический язык собственного изобретения

Так можно вообще без циклов обойтись. Если известно, что СтаршийБит = log_2 (Число), то можно отделить две битовые половинки числа и заXORить их друг с другом. Если в результате 0, значит симметрия. Или вот так:

Использую всё тот же интуитивно понятный алгоритмический язык собственного изобретения

На 1С похоже

С XOR не получится, как бы этого не хотелось. Контрпример, число с 1 в начале и 1 в конце и множеством нулей всередине. Скажем 1000001. XORим мы тогда 1000 и 0001, что даёт 1001.

По поводу приведёного алгоритма: я что-то не очень понял, как он должне работать.
Если исходное число, скажем, было 1001, а 255 в бинарном представлении это 8 единичек, то ДвеЛевыеПоловинки = 10 + 1111111100 = 1111111110, что не равно исходному числу.

Без инверсирования числа, либо без битового обхода с двух концов, эту задачу никак не решить, как я понял. Оба варинты по интуитивности равны, а по скорости иверсирование несколько быстее, так как длину числа не нужно вычислять. Но всё равно сложность обоих алгоритмов будет O(N). Линейной сложности никак не добиться.

Если исходное число, скажем, было 1001

Недописал, потерял мысль)) Вот как я хотел:

ДвеЛевыеПоловинки = (Число >> (СтаршийБит >> 1)) + (Число & (255 << (СтаршийБит >> 1)));

Но тут я забыл, что вторая половинка все равно не развернута. Но все-таки где-то внутри я чувствую что можно без циклов, подумаю на досуге.