Periodical binary representation

Question

How can I make a program that checks if binary representation of a given integer is periodical with period length m >= 2?

For example:

Binary representation of 10 is periodical

10 base 10 = 1010 base 2, periodical with period length 2

Binary representation of 9 is not periodical

9 base 10 = 1001 base 2

Binary representation of 153 is periodical

153 base 10 = 10011001 base 2, periodical with period length 4

Is there any specific algorithm for doing this?

I am working in C++.

Answer 1

What you can do is rotate the bits and check each time if the numbers are equal. i.e. the rotated one and the one you start with

// 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";

The complexity is linear in the number of bits.