C code to calculate the binary period of an integer
$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.
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
$endgroup$
|
show 5 more comments
$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.
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
$endgroup$
$begingroup$
i thinkfor(i = 0; i < (l - l/2); i++){
should befor(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
|
show 5 more comments
$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.
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
$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.
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
c
edited Jul 5 '18 at 14:14
Malachi♦
25.6k774177
25.6k774177
asked Jul 4 '18 at 12:59
hagohago
7817
7817
$begingroup$
i thinkfor(i = 0; i < (l - l/2); i++){
should befor(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
|
show 5 more comments
$begingroup$
i thinkfor(i = 0; i < (l - l/2); i++){
should befor(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
|
show 5 more comments
2 Answers
2
active
oldest
votes
$begingroup$
I see some things that may help you improve your program.
Use the appropriate #include
s
In order to compile and link, this code requires at least #include <stdio.h>
. For the program to be complete, all appropriate #include
s 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.
$endgroup$
$begingroup$
You could also useint_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
add a comment |
$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;
}
$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 is100000
binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initialmask
calculation and thefor
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 withperiod = 2
.
$endgroup$
– Edward
Jul 4 '18 at 23:57
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$begingroup$
I see some things that may help you improve your program.
Use the appropriate #include
s
In order to compile and link, this code requires at least #include <stdio.h>
. For the program to be complete, all appropriate #include
s 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.
$endgroup$
$begingroup$
You could also useint_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
add a comment |
$begingroup$
I see some things that may help you improve your program.
Use the appropriate #include
s
In order to compile and link, this code requires at least #include <stdio.h>
. For the program to be complete, all appropriate #include
s 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.
$endgroup$
$begingroup$
You could also useint_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
add a comment |
$begingroup$
I see some things that may help you improve your program.
Use the appropriate #include
s
In order to compile and link, this code requires at least #include <stdio.h>
. For the program to be complete, all appropriate #include
s 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.
$endgroup$
I see some things that may help you improve your program.
Use the appropriate #include
s
In order to compile and link, this code requires at least #include <stdio.h>
. For the program to be complete, all appropriate #include
s 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.
answered Jul 4 '18 at 16:35
EdwardEdward
47.5k378213
47.5k378213
$begingroup$
You could also useint_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
add a comment |
$begingroup$
You could also useint_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
add a comment |
$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;
}
$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 is100000
binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initialmask
calculation and thefor
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 withperiod = 2
.
$endgroup$
– Edward
Jul 4 '18 at 23:57
add a comment |
$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;
}
$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 is100000
binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initialmask
calculation and thefor
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 withperiod = 2
.
$endgroup$
– Edward
Jul 4 '18 at 23:57
add a comment |
$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;
}
$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;
}
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 is100000
binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initialmask
calculation and thefor
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 withperiod = 2
.
$endgroup$
– Edward
Jul 4 '18 at 23:57
add a comment |
$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 is100000
binary. Then we subtract one to get 5 ones. In fact, we can speed this code a bit by inserting this between the initialmask
calculation and thefor
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 withperiod = 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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$begingroup$
i think
for(i = 0; i < (l - l/2); i++){
should befor(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