Задача

Циклический сдвиг

Запишем целое десятичное число $n$ в двоичной системе счисления и образуем все левые циклические сдвиги числа $n$, у которых первая цифра числа переносится в конец.

Например, если $n = 11$, то в двоичной системе это $1011$_$2$, его циклические сдвиги: $0111$_$2$, $1110$_$2$, $1101$_$2$, $1011$_$2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110$_$2$ $=$ $14$_$10$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n \left(1 ≤ n ≤ 2 \cdot 10^9\right)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные	Выходные данные
11	14
23	30
256	256
257	384
34132	43664

Код программы

#include <iostream>
using namespace std;

int main(){
    unsigned long in_val, tmp_val, power = 1;
    cin >> in_val;
    tmp_val = in_val;
    while(tmp_val){
        tmp_val /= 2;
        power *= 2;
    }
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if (max_val < in_val) max_val = in_val;
    }while (tmp_val != in_val );
    cout << max_val << endl;
    
    return 0;
}

#include <iostream>

using namespace std;

int main(){

unsigned long in_val, tmp_val, power = 1;

cin >> in_val;

tmp_val = in_val;

while(tmp_val){

tmp_val /= 2;

power *= 2;

}

tmp_val = in_val;

unsigned long max_val = in_val;

do{

in_val = in_val << 1;

in_val = in_val % power + (in_val >= power ? 1 : 0);

if (max_val < in_val) max_val = in_val;

}while (tmp_val != in_val );

cout << max_val << endl;

return 0;

}

Решение задачи

Сначала мы находим степень двойки, большую данного числа;
Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Возможный вариант решения задачи

Возможно избавиться от первого цикла путем нахождения количества двоичных разрядов кратных степени двойки с помощью:
1. взятия логарифма числа по основанию $2$ с последующим округлением до целого;
2. возведение двойки в степень, полученную выше, и увеличенную на единицу.
То есть $2^{\lfloor \log_{2}n \rfloor + 1}$.

Тогда код будет выглядеть так:

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    unsigned long in_val, tmp_val;
    cin >> in_val;
    tmp_val = in_val;
    unsigned long power;
    power = pow(2, floor(log2(in_val)) + 1);
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if(max_val < in_val){
            max_val = in_val;
        }
    }while(tmp_val != in_val);
    cout << max_val << endl;

    return 0;
}