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.

enter image description here

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

• Mark Jeronimus: i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
• hago: @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
• Mike Borkland: 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++.
• Malachi: 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: @Hago, I have edited your question, if I have lost any understanding please let me know.

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.

• gyre: You could also use int_fast32_t
• hago: @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++)

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

• hago: Thanks.. But how do you calculate the mask? or why do we need this mask?
• Edward: 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;
• Edward: It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
• Edward: I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.