Циклический сдвиг вправо двоичного кода

Question

Всем доброго дня! Суть проблемы в цледующем: есть некое число n и его двоичное предсавление, после некоторого количество цыкличных сдвигов вправо двоичное представление сново повтаряется, и нужно выяснить максималное число которое получается из десятичного представления одного из этих сдвигов.

Вот что я пробовал делать

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>

using namespace std;

const int N = 1005;

string to_binary(int x) {
    string s;
    do {
        s.push_back('0' + (x & 1));
    } while (x >>= 1);

    reverse(s.begin(), s.end());
    return s;
}

int get_count_of_repeats(string s) {
    if (s.size() == 1) {
        return 0;
    }
    else {
        string z = s;
        int count = 1;

        char c = z[z.size() - 1];
        for (int i = z.size() - 1; i >= 1; i--) {
            z[i] = z[i - 1];
        }
        z[0] = c;

        while (s != z) {
            char ch = z[z.size() - 1];
            for (int i = z.size() - 1; i >= 1; i--) {
                z[i] = z[i - 1];
            }
            z[0] = ch;
            count++;
        }
        return count;
    }
}


int main() {

    int n;
    cin >> n;

    string binary = to_binary(n);

    if (get_count_of_repeats(binary) == 0) {
        cout << n << endl;
    }
    else {
        int mx = -1000007;
        int count = get_count_of_repeats(binary);
        for (int i = 0; i < count; i++) {
            string z = binary;
            char c = z[z.size() - 1];
            for (int j = z.size() - 1; j >= 1; j--) {
                z[i] = z[i - 1];
            }
            z[0] = c;

            mx = max(mx, stoi(z, nullptr, 2));
            binary = z;
        }
        cout << mx << endl;
    }


    return 0;
}

но мне выдает следующую ошибку

помогите пожалуйста решить проблему

Answer 1

В main

 for (int j = z.size() - 1; j >= 1; j--) {
            z[i] = z[i - 1];
        }

должно быть

for (int j = z.size() - 1; j >= 1; j--) {
            z[j] = z[j - 1];
        }

Копипаст и однобуквенные переменные плохую службу сослужили

Answer 2

Задача естественным образом решается без всяких преобразований числа в строку символов, применением к самому числу (целой переменной) операций для побитового сдвига (>> и <<) и операции |.

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

#include <iostream>
#include <limits.h>  // CHAR_BIT definition

using namespace std;  
  

int main () {
  unsigned int n,
    shift_size = sizeof(n) * CHAR_BIT - 1;  // number of bits in the number minus one

  if (cin >> n) {
    unsigned int max_val = n,
      v = n;

    do {
      v = (v >> 1) | (v << shift_size); // rotate to right
      //v = (v << 1) | (v >> shift_size); // rotate to left
      if (v > max_val)
        max_val = v;
    } while (n != v);

    cout << "max = " << max_val  << '\n';
  } else 
    cout << "Nothing to do (not number)\n";
}

Если циклический сдвиг нужно делать только на диапазоне значащих бит исходного числа (например, для числа 5 (101b) это 3 бита), то добавим функцию, вычисляющую этот диапазон

// ugly implementation of FFS, but simple and short
unsigned int get_bitsize (unsigned int n) {
  unsigned int i;
  for (i = 0; n; n >>= 1, i++);

  return i;
}

величину сдвига для вращения вычислим как shift_size = get_bitsize(n) - 1

а сам сдвиг вправо будем делать с маскированием "лишних" (получающихся в результате сдвига) бит -- ((v >> 1) | (v << shift_size)) & mask),

где mask состоит из бит, равных 1 для диапазона.
(степень двойки (т.е. 1 << get_bitsize(n)) минус 1 делает соответствующую маску).

В общем, получаем вот такую часть кода для перебора

  if (cin >> n) {
      
    unsigned int size = get_bitsize(n),
      shift_size = size - 1, 
      mask = size == sizeof(n) * CHAR_BIT ? ~0 : (1 << size) - 1;
    
    unsigned int max_val = n,
      v = n;

    if (size > 1)
      do {
        v = ((v >> 1) | (v << shift_size)) & mask; // rotate to right
        if (v > max_val)
          max_val = v;
      } while (n != v);

    cout << "max = " << max_val << '\n';
  }

БЛОГ НА HUSL

Циклический сдвиг вправо двоичного кода

Ответы (2 шт):