C code to calculate the binary period of an integer

Question

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

Answer 1

I see some things that may help you improve your program.

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.

Check your assumptions

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

Format your code consistently

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.

Answer 2

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;
        mask >>= 1;
        if (((n ^ shifted) & mask) == 0) {
            return period;
        }
    }
    return -1;
}