C code to calculate the binary period of an integer












9












$begingroup$



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("%dn",solution(102));
printf("%dn",solution(955));
printf("%dn",solution(1651));
return 0;
}









share|improve this question











$endgroup$












  • $begingroup$
    i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
    $endgroup$
    – Mark Jeronimus
    Jul 4 '18 at 13:40






  • 1




    $begingroup$
    @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
    $endgroup$
    – hago
    Jul 4 '18 at 13:59






  • 3




    $begingroup$
    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++.
    $endgroup$
    – Mike Borkland
    Jul 4 '18 at 14:22






  • 1




    $begingroup$
    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.
    $endgroup$
    – Malachi
    Jul 4 '18 at 16:43






  • 1




    $begingroup$
    @Hago, I have edited your question, if I have lost any understanding please let me know.
    $endgroup$
    – Malachi
    Jul 5 '18 at 14:15
















9












$begingroup$



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("%dn",solution(102));
printf("%dn",solution(955));
printf("%dn",solution(1651));
return 0;
}









share|improve this question











$endgroup$












  • $begingroup$
    i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
    $endgroup$
    – Mark Jeronimus
    Jul 4 '18 at 13:40






  • 1




    $begingroup$
    @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
    $endgroup$
    – hago
    Jul 4 '18 at 13:59






  • 3




    $begingroup$
    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++.
    $endgroup$
    – Mike Borkland
    Jul 4 '18 at 14:22






  • 1




    $begingroup$
    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.
    $endgroup$
    – Malachi
    Jul 4 '18 at 16:43






  • 1




    $begingroup$
    @Hago, I have edited your question, if I have lost any understanding please let me know.
    $endgroup$
    – Malachi
    Jul 5 '18 at 14:15














9












9








9





$begingroup$



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("%dn",solution(102));
printf("%dn",solution(955));
printf("%dn",solution(1651));
return 0;
}









share|improve this question











$endgroup$





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("%dn",solution(102));
printf("%dn",solution(955));
printf("%dn",solution(1651));
return 0;
}






c






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jul 5 '18 at 14:14









Malachi

25.6k774177




25.6k774177










asked Jul 4 '18 at 12:59









hagohago

7817




7817












  • $begingroup$
    i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
    $endgroup$
    – Mark Jeronimus
    Jul 4 '18 at 13:40






  • 1




    $begingroup$
    @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
    $endgroup$
    – hago
    Jul 4 '18 at 13:59






  • 3




    $begingroup$
    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++.
    $endgroup$
    – Mike Borkland
    Jul 4 '18 at 14:22






  • 1




    $begingroup$
    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.
    $endgroup$
    – Malachi
    Jul 4 '18 at 16:43






  • 1




    $begingroup$
    @Hago, I have edited your question, if I have lost any understanding please let me know.
    $endgroup$
    – Malachi
    Jul 5 '18 at 14:15


















  • $begingroup$
    i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
    $endgroup$
    – Mark Jeronimus
    Jul 4 '18 at 13:40






  • 1




    $begingroup$
    @MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
    $endgroup$
    – hago
    Jul 4 '18 at 13:59






  • 3




    $begingroup$
    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++.
    $endgroup$
    – Mike Borkland
    Jul 4 '18 at 14:22






  • 1




    $begingroup$
    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.
    $endgroup$
    – Malachi
    Jul 4 '18 at 16:43






  • 1




    $begingroup$
    @Hago, I have edited your question, if I have lost any understanding please let me know.
    $endgroup$
    – Malachi
    Jul 5 '18 at 14:15
















$begingroup$
i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
$endgroup$
– Mark Jeronimus
Jul 4 '18 at 13:40




$begingroup$
i think for(i = 0; i < (l - l/2); i++){ should be for(i = 0; i < l-p; i++){
$endgroup$
– Mark Jeronimus
Jul 4 '18 at 13:40




1




1




$begingroup$
@MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
$endgroup$
– hago
Jul 4 '18 at 13:59




$begingroup$
@MarkJeronimus, from the question I thought it ranges from 0 to half of the length?
$endgroup$
– hago
Jul 4 '18 at 13:59




3




3




$begingroup$
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++.
$endgroup$
– Mike Borkland
Jul 4 '18 at 14:22




$begingroup$
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++.
$endgroup$
– Mike Borkland
Jul 4 '18 at 14:22




1




1




$begingroup$
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.
$endgroup$
– Malachi
Jul 4 '18 at 16:43




$begingroup$
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.
$endgroup$
– Malachi
Jul 4 '18 at 16:43




1




1




$begingroup$
@Hago, I have edited your question, if I have lost any understanding please let me know.
$endgroup$
– Malachi
Jul 5 '18 at 14:15




$begingroup$
@Hago, I have edited your question, if I have lost any understanding please let me know.
$endgroup$
– Malachi
Jul 5 '18 at 14:15










2 Answers
2






active

oldest

votes


















5












$begingroup$

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.






share|improve this answer









$endgroup$













  • $begingroup$
    You could also use int_fast32_t
    $endgroup$
    – gyre
    Jul 4 '18 at 20:34










  • $begingroup$
    @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++)
    $endgroup$
    – hago
    Jul 5 '18 at 10:58





















5












$begingroup$

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





share|improve this answer









$endgroup$













  • $begingroup$
    Thanks.. But how do you calculate the mask? or why do we need this mask?
    $endgroup$
    – hago
    Jul 4 '18 at 22:24












  • $begingroup$
    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;
    $endgroup$
    – Edward
    Jul 4 '18 at 22:59












  • $begingroup$
    It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:02










  • $begingroup$
    I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:57











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f197807%2fc-code-to-calculate-the-binary-period-of-an-integer%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









5












$begingroup$

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.






share|improve this answer









$endgroup$













  • $begingroup$
    You could also use int_fast32_t
    $endgroup$
    – gyre
    Jul 4 '18 at 20:34










  • $begingroup$
    @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++)
    $endgroup$
    – hago
    Jul 5 '18 at 10:58


















5












$begingroup$

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.






share|improve this answer









$endgroup$













  • $begingroup$
    You could also use int_fast32_t
    $endgroup$
    – gyre
    Jul 4 '18 at 20:34










  • $begingroup$
    @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++)
    $endgroup$
    – hago
    Jul 5 '18 at 10:58
















5












5








5





$begingroup$

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.






share|improve this answer









$endgroup$



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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Jul 4 '18 at 16:35









EdwardEdward

47.5k378213




47.5k378213












  • $begingroup$
    You could also use int_fast32_t
    $endgroup$
    – gyre
    Jul 4 '18 at 20:34










  • $begingroup$
    @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++)
    $endgroup$
    – hago
    Jul 5 '18 at 10:58




















  • $begingroup$
    You could also use int_fast32_t
    $endgroup$
    – gyre
    Jul 4 '18 at 20:34










  • $begingroup$
    @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++)
    $endgroup$
    – hago
    Jul 5 '18 at 10:58


















$begingroup$
You could also use int_fast32_t
$endgroup$
– gyre
Jul 4 '18 at 20:34




$begingroup$
You could also use int_fast32_t
$endgroup$
– gyre
Jul 4 '18 at 20:34












$begingroup$
@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++)
$endgroup$
– hago
Jul 5 '18 at 10:58






$begingroup$
@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++)
$endgroup$
– hago
Jul 5 '18 at 10:58















5












$begingroup$

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





share|improve this answer









$endgroup$













  • $begingroup$
    Thanks.. But how do you calculate the mask? or why do we need this mask?
    $endgroup$
    – hago
    Jul 4 '18 at 22:24












  • $begingroup$
    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;
    $endgroup$
    – Edward
    Jul 4 '18 at 22:59












  • $begingroup$
    It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:02










  • $begingroup$
    I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:57
















5












$begingroup$

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





share|improve this answer









$endgroup$













  • $begingroup$
    Thanks.. But how do you calculate the mask? or why do we need this mask?
    $endgroup$
    – hago
    Jul 4 '18 at 22:24












  • $begingroup$
    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;
    $endgroup$
    – Edward
    Jul 4 '18 at 22:59












  • $begingroup$
    It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:02










  • $begingroup$
    I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:57














5












5








5





$begingroup$

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





share|improve this answer









$endgroup$



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






share|improve this answer












share|improve this answer



share|improve this answer










answered Jul 4 '18 at 18:51









Martin RMartin R

16.2k12366




16.2k12366












  • $begingroup$
    Thanks.. But how do you calculate the mask? or why do we need this mask?
    $endgroup$
    – hago
    Jul 4 '18 at 22:24












  • $begingroup$
    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;
    $endgroup$
    – Edward
    Jul 4 '18 at 22:59












  • $begingroup$
    It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:02










  • $begingroup$
    I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:57


















  • $begingroup$
    Thanks.. But how do you calculate the mask? or why do we need this mask?
    $endgroup$
    – hago
    Jul 4 '18 at 22:24












  • $begingroup$
    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;
    $endgroup$
    – Edward
    Jul 4 '18 at 22:59












  • $begingroup$
    It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:02










  • $begingroup$
    I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
    $endgroup$
    – Edward
    Jul 4 '18 at 23:57
















$begingroup$
Thanks.. But how do you calculate the mask? or why do we need this mask?
$endgroup$
– hago
Jul 4 '18 at 22:24






$begingroup$
Thanks.. But how do you calculate the mask? or why do we need this mask?
$endgroup$
– hago
Jul 4 '18 at 22:24














$begingroup$
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;
$endgroup$
– Edward
Jul 4 '18 at 22:59






$begingroup$
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;
$endgroup$
– Edward
Jul 4 '18 at 22:59














$begingroup$
It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
$endgroup$
– Edward
Jul 4 '18 at 23:02




$begingroup$
It's called a mask because we only want to "mask off" particular bits for examination. Think of using masking tape and spray paint.
$endgroup$
– Edward
Jul 4 '18 at 23:02












$begingroup$
I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
$endgroup$
– Edward
Jul 4 '18 at 23:57




$begingroup$
I should have mentioned that the speedup I mentioned earlier also requires that the for loop is changed to start with period = 2.
$endgroup$
– Edward
Jul 4 '18 at 23:57


















draft saved

draft discarded




















































Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f197807%2fc-code-to-calculate-the-binary-period-of-an-integer%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

How to make a Squid Proxy server?

Is this a new Fibonacci Identity?

Touch on Surface Book