Периодическое двоичное представление
Как я могу создать программу, которая проверяет, является ли двоичное представление заданного целого числа периодическим с периодом m> = 2?
Например:
Двоичное представление 10 периодическое
10 base 10 = 1010 base 2, periodical with period length 2
Двоичное представление 9 не является периодическим
9 base 10 = 1001 base 2
Двоичное представление 153 является периодическим
153 base 10 = 10011001 base 2, periodical with period length 4
Есть ли какой-то конкретный алгоритм для этого?
Я работаю в C ++.
Решение
Что вы можете сделать, это повернуть биты и каждый раз проверять, равны ли числа. то есть повернутый и тот, с которого вы начинаете
// it is being assumed the size of int is 4bytes
int num = 153;
int temp = num;
int i = 0;
for (i=0; i<(8*sizeof(int))/2; i++){
temp = ((temp >> 1) & LONG_MAX | temp << 31) // rotate the bits by 1
if (!(temp ^ num)){ // check if the numbers are the same
break;
}
}
if (i<(8*sizeof(int))/2)
std::cout << "Period is" << i << "\n";
else
std::cout << "Not periodic";
Сложность линейна по количеству битов.
Другие решения
KMP — это специальный алгоритм для нахождения периода любой строки, источника, включая двоичное представление числа, которое является просто строкой. Это работает в O (N) время.
#include <iostream>
#include <algorithm>
using namespace std;
int calc_period(string s) {
vector<int> pre(s.size());
// this condition is keeped true in the for-loop:
// s[0..pre[i]] is this longest suffix of s[0..i] in s[0..i]'s all prefixes (if pre[i] >= 0)
int k = -1;
pre[0] = -1;
for (int i = 1; i < int(s.size()); ++i) {
while (k >= 0 && s[k + 1] != s[i]) {
k = pre[k];
}
if (s[k + 1] == s[i]) {
++k;
}
pre[i] = k;
}
int l = s.size() - 1 - pre[s.size() - 1];
return s.size() % l == 0 ? s.size() / l : 1;
}
string to_binary(long long x) {
string s;
if (x == 0) {
s = "0";
} else {
while (x) {
s += (x & 1) ? "1" : "0";
x >>= 1;
}
reverse(s.begin(), s.end());
}
return s;
}
int main() {
int x;
cin >> x;
cout << calc_period(to_binary(x)) << endl;
return 0;
}
Вы можете попробовать этот код, чтобы увидеть, как он работает. Если вы хотите узнать больше о KMP, прочитайте его вики-страница или связанные учебники, такие как «Введение в алгоритм».