# C code to calculate the binary period of an integer

A non-empty zero-indexed string S consisting of Q characters is given. The period of this string is the smallest positive integer P such that:

$P ≤ Q/2$ and $S[K] = S[K+P]$ for $0 ≤ K < Q−P.$

So for example, for the integers 955,1651 and 102, convert the numbers to binary and the function should return 4,5,-1 respectively.

The function returns -1 if there is no binary period for the given integer.

The int n can be any value between 1 to 99999999

Here is the original code given in the challenge. The Challenge states that by modifying at most 2 lines, in the function solution, the existing bug should be fixed.

Here is my Solution, Can someone please review this?

int solution(int n)
{
int d[30];
int l = 0;
int p;
//convert the integer to binary
while(n > 0)
{
d[l]= n %2 ;
n = n /2;
l++;
}
//compute the length of the resulting binary number
//and that is stored in the variable l

for(p = l/2; p >0; p--){
int ok = 1;
int i;
for(i = 0; i < (l - l/2); i++){
if(d[i] != d[i + p]){
ok = 0;
break;
}
}
if(ok){
return p;
}
}
return -1;
}

int main(int argc, char** argv) {
printf("%d\n",solution(102));
printf("%d\n",solution(955));
printf("%d\n",solution(1651));
return 0;
}

• i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){ Jul 4, 2018 at 13:40
• @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
– hago
Jul 4, 2018 at 13:59
• Please don't use both the C and C++ tags. They are very different languages. A C++ review of your code would be quite different from a C review. In fact, your code looks nothing like modern C++. Jul 4, 2018 at 14:22
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Malachi
Jul 4, 2018 at 16:43
• @Hago, I have edited your question, if I have lost any understanding please let me know.
– Malachi
Jul 5, 2018 at 14:15

## Use the appropriate #includes

In order to compile and link, this code requires at least #include <stdio.h>. For the program to be complete, all appropriate #includes should be listed, too.

For this code to work, the int on your platform must be at least 32 bits. For that reason, this assumption should be checked at compile time:

static_assert(sizeof(int) >= 4), "int must be at least 32 bits");


It doesn't matter as much what style you use as it matters that you have a consistent style. In particular, there seems to be inconsistent indenting and inconsistent placement of braces. Using a consistent style helps readers of the code understand it.

## Use better variable names

Generally, single letter variable names other than i and j for loop variables, are best avoided in favor of longer, more descriptive names. The variable p is not too terrible, but the variable l is definitely a poor choice, not least because it's easily mistaken for the digit 1 or the letter i. I changed it to len in the rewrite I did.

## Fix the bug

Right now, if we have the program calculate solution(8), it returns 1 instead of -1. That is not correct. There are other values within the range that also return incorrect values.

## Write a test program

Right now the main routine just tries three values. It would be better to try other values, maybe even every value in the range, and test it for accuracy. You can do that by creating a function bool verify(int n, int p) that returns true if the condition stated at the beginning of the problem is true.

• You could also use int_fast32_t
– gyre
Jul 4, 2018 at 20:34
• @Edward, Thanks. I tried solving the bug and ended up finding that the outer for loop has to be modified as follows: The outer for loops needs to be modified as int Period = length /2; for(p = 1 ; p < (Period + 1); p++)
– hago
Jul 5, 2018 at 10:58

Your solution stores the base-2 representation of the given number in an array, and then uses two nested loops to determine the period.

This can be done more efficiently by taking advantage of bitwise operations.

Let's take $n = 955_{10} = 1110111011_{2}$ as an example. To determine the period, we shift $n$ to the right until all “significant” bits of the shifted number coincide with the corresponding bits of $n$. In our example, this happens after shifting by 4 positions:

1110111011  (n)
111011101  (n >> 1)
11101110  (n >> 2)
1110111  (n >> 3)
111011  (n >> 4)


This condition can be checked with a single expression

((n ^ (n >> p)) & mask) == 0


using bitwise XOR, AND, and a suitable mask consisting of 1's at all significant bit positions of n >> p.

This makes the array obsolete, and only a simple loop is needed instead of a nested loop. An implementation could look like this:

int solution(int n) {

// Compute the length of the binary number.
int len = 0;
for (int i = n; i > 0; i >>= 1) {
len++;
}

int shifted = n; // n shifted by period bit positions to the right
int mask = (1 << len) - 1; // Corresponding bit mask

for (int period = 1; period <= len/2; period++) {
shifted >>= 1;

• The mask is calculated like this: if we want a mask for 5 bits, we calculate (1 << 5) which is 100000 binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initial mask calculation and the for loop: if (n == mask) { return len < 2 ? -1 : 1; } shifted >>= 1; mask >>= 1;  Jul 4, 2018 at 22:59
• I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2. Jul 4, 2018 at 23:57