Что не так с алгоритмом создания максимального числа из исходного, используя двоичную СС?

Question

[fjaerj12]

Задача
Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 10011.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011
…
и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28.

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

Входные данные
Входной файл INPUT.TXT содержит одно целое число N (0 ≤ N ≤ 32767).

Выходные данные
Ваша программа должна вывести в выходной файл OUTPUT.TXT одно целое число, равное результату игры.

Примеры
№ INPUT.TXT OUTPUT.TXT
1 19 28
2 1212 1938

Задумка
Узнаём число разрядов числа, записываем их, дублируем их несколько раз. Потом ищем место, где самое большое скопление единиц, переводим в десятичную СС, выводим.

#include <iostream>
#include <string>
#include <cmath>

int main()
{
    int number = 0, binarCount = 0;
    std::cin >> number;
    std::string binarForm;
    
    int q = 0;
    while (number > 0) 
    {
        binarForm.push_back(number % 2);
        q++;
        number /= 2;
        binarCount++;
    }
    
    for (int i = binarCount - 1; i > -1; i--)
    {
        binarForm.push_back(binarForm[i]);
        q++;
    }
    for (int i = binarCount - 1; i > -1; i--)
    {
        binarForm.push_back(binarForm[i]);
        q++;
    }
    for (int i = binarCount - 1; i > -1; i--)
    {
        binarForm.push_back(binarForm[i]);
        q++;
    }

    int count = 0, number1 = 0, countNumberOne = 0, iteratorNumber = 0;
    for (int i = binarCount; i < 3 * binarCount - 1; i++)
    {
        count++;
        if (binarForm[i] == 1)
        {
            countNumberOne++;
            for (int j = i + 1; j < 3 * binarCount; j++)
            {
                if (binarForm[j] == 1)
                {
                    countNumberOne++;
                }
                if (binarForm[j] == 0)
                {
                    break;
                }
            }

            if (countNumberOne >= number1)
            {
                number1 = countNumberOne;
                iteratorNumber = count - 1;
            }
            countNumberOne = 0;
        }    
    }

    int result = 0, copyBinarCount = binarCount;
    for (int k = copyBinarCount + iteratorNumber; k < 2 * copyBinarCount + iteratorNumber; k++)
    {
        result += pow(2, binarCount - 1) * binarForm[k];
        binarCount--;
    }
    std::cout << result;
}

Answer 1

[Wataru]

Потому что нельзя просто искать максимальное скопление единиц. Их может быть несколько - какое из них выбирать зависит от того, что идет после них. Например вот такое число в двоичной системе: 1001110100101110110.

Тут есть 2 куска 1110. Но за первым идет "010", а за вторым "011". Начинать со второго - выгоднее.

В этой задаче очень маленькие ограничения - можно полностью перебирать все возможные числа и брать максимальное. Можно даже не переводить в двоичную систему, а воспользоваться битовыми операциями.
Когда вы узнали, сколько битов в числе, то самый младший бит x можно получить как x&1. Сдвинуть все биты числа на одну позицию вправо - это x >> 1. При этом младший бит пропадает. Чтобы вставить новый бит b слева нужно сделать x | (b << k) - тут k - номер позиции этого бита, считая с 0.

Используя эти операции вы можете просто в цикле получать следующее число после циклического сдвига и из них искать максимум. Только сначала узнайте, сколько всего бит в числе.

И так, для развития: Если бы ограничения были слишком большие (число в десятки тысяч бит), то тут пришлось бы применять умные строковые алгоритмы. Это была бы задача на поиск лексикографически максимального циклического сдвига. Решается с помощью суффиксного дерева, суффиксного массива или суффиксного автомата.

Comments

[longclaps]

Если бы ограничения были слишком большие (число в десятки тысяч бит)

def f(n):
    le = n.bit_length() - 1
    big_one = 1 << le
    res = n
    for _ in range(le):
        n = (n >> 1) | big_one if n & 1 else n >> 1
        if res < n:
            res = n
    return res

from random import randrange

f(randrange(1 << 10_000))

0.009619 секунд на моей старушке.

[Wataru]

longclaps, А теперь введите 90000. Уже будет работать почти дольше секунды. Это решение квадратичное, когда как суффиксные алгоритмы будут линейные. Но, да, надо было сказать сотни тысяч, вместо десятков. Так было бы надежнее.