主页 / 问题 / 1168914
Accepted
E_d_u_a_r_d
Asked:2020-08-22 03:18:59 +0000 UTC2020-08-22 03:18:59 +0000 UTC

向右旋转二进制代码

  • 772

今天是个好日子！问题实质如下：有一个数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;
}

但它给了我以下错误

在此处输入图像描述

请帮我解决问题

c++

2 个回答

  1. Best Answer

    主要是

     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];
        }

    复制粘贴和单字母变量造成了损害

    • 3

  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 的位组成。
    （2 的幂（即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';
  }
    • 3

相关问题