Mixing
Binary Addition Algorithm
$begingroup$
I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n.
X = binary representation of 0.
for i ← 1 to n
starting from right to left in X , find the first digit that is 0 and assume it is the kth digit
X ← flip the kth digit of X to 1 and flip 1,2,...,(k−1)th digit of X to 0
print X
We are thus incrementing by 1 n number of times.
Essentially, the number of bit operations depends on the value of k in each iteration, but I can't seem to find a pattern for the first bit which is zero from the binary representation of 1,2,3...n. Any help?
algorithms computational-complexity
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
$endgroup$
add a comment |
$begingroup$
I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n.
X = binary representation of 0.
for i ← 1 to n
starting from right to left in X , find the first digit that is 0 and assume it is the kth digit
X ← flip the kth digit of X to 1 and flip 1,2,...,(k−1)th digit of X to 0
print X
We are thus incrementing by 1 n number of times.
Essentially, the number of bit operations depends on the value of k in each iteration, but I can't seem to find a pattern for the first bit which is zero from the binary representation of 1,2,3...n. Any help?
algorithms computational-complexity
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
$endgroup$
$begingroup$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44
add a comment |
$begingroup$
I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n.
X = binary representation of 0.
for i ← 1 to n
starting from right to left in X , find the first digit that is 0 and assume it is the kth digit
X ← flip the kth digit of X to 1 and flip 1,2,...,(k−1)th digit of X to 0
print X
We are thus incrementing by 1 n number of times.
Essentially, the number of bit operations depends on the value of k in each iteration, but I can't seem to find a pattern for the first bit which is zero from the binary representation of 1,2,3...n. Any help?
algorithms computational-complexity
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
$endgroup$
I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n.
X = binary representation of 0.
for i ← 1 to n
starting from right to left in X , find the first digit that is 0 and assume it is the kth digit
X ← flip the kth digit of X to 1 and flip 1,2,...,(k−1)th digit of X to 0
print X
We are thus incrementing by 1 n number of times.
Essentially, the number of bit operations depends on the value of k in each iteration, but I can't seem to find a pattern for the first bit which is zero from the binary representation of 1,2,3...n. Any help?
algorithms computational-complexity
algorithms computational-complexity
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
edited Jan 17 at 3:28
Einstein the troll
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
asked Jan 17 at 3:03
Einstein the trollEinstein the troll
144210
144210
$begingroup$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44
add a comment |
$begingroup$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44
$begingroup$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)
There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, dots$$ which you can sort of see a pattern in.
But for your problem, we don't really need a formula. Instead, it's enough to observe that:
- At least $frac12$ of the values $0,1,2,dots,n-1$ end in $dots0$. (And take one operation to increment.)
- At least $frac14$ of them end in $dots01$. (And take two operations to increment.)
- At least $frac18$ of them end in $dots011$. (And take three operations to increment.)
And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than
$$
frac12 cdot 1 + frac14 cdot 2 + frac18 cdot 3 + dots = sum_{i=1}^infty frac{i}{2^i} = 2.
$$
In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
$endgroup$
add a comment |
$begingroup$
Normally we are looking for an upper bound on the number of operations. In this case there will be $lfloor log_2(X) rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
$endgroup$
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.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3076549%2fbinary-addition-algorithm%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$
The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)
There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, dots$$ which you can sort of see a pattern in.
But for your problem, we don't really need a formula. Instead, it's enough to observe that:
- At least $frac12$ of the values $0,1,2,dots,n-1$ end in $dots0$. (And take one operation to increment.)
- At least $frac14$ of them end in $dots01$. (And take two operations to increment.)
- At least $frac18$ of them end in $dots011$. (And take three operations to increment.)
And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than
$$
frac12 cdot 1 + frac14 cdot 2 + frac18 cdot 3 + dots = sum_{i=1}^infty frac{i}{2^i} = 2.
$$
In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
$endgroup$
add a comment |
$begingroup$
The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)
There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, dots$$ which you can sort of see a pattern in.
But for your problem, we don't really need a formula. Instead, it's enough to observe that:
- At least $frac12$ of the values $0,1,2,dots,n-1$ end in $dots0$. (And take one operation to increment.)
- At least $frac14$ of them end in $dots01$. (And take two operations to increment.)
- At least $frac18$ of them end in $dots011$. (And take three operations to increment.)
And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than
$$
frac12 cdot 1 + frac14 cdot 2 + frac18 cdot 3 + dots = sum_{i=1}^infty frac{i}{2^i} = 2.
$$
In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
$endgroup$
add a comment |
$begingroup$
The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)
There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, dots$$ which you can sort of see a pattern in.
But for your problem, we don't really need a formula. Instead, it's enough to observe that:
- At least $frac12$ of the values $0,1,2,dots,n-1$ end in $dots0$. (And take one operation to increment.)
- At least $frac14$ of them end in $dots01$. (And take two operations to increment.)
- At least $frac18$ of them end in $dots011$. (And take three operations to increment.)
And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than
$$
frac12 cdot 1 + frac14 cdot 2 + frac18 cdot 3 + dots = sum_{i=1}^infty frac{i}{2^i} = 2.
$$
In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
$endgroup$
The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)
There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, dots$$ which you can sort of see a pattern in.
But for your problem, we don't really need a formula. Instead, it's enough to observe that:
- At least $frac12$ of the values $0,1,2,dots,n-1$ end in $dots0$. (And take one operation to increment.)
- At least $frac14$ of them end in $dots01$. (And take two operations to increment.)
- At least $frac18$ of them end in $dots011$. (And take three operations to increment.)
And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than
$$
frac12 cdot 1 + frac14 cdot 2 + frac18 cdot 3 + dots = sum_{i=1}^infty frac{i}{2^i} = 2.
$$
In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
answered Jan 18 at 3:29
Misha LavrovMisha Lavrov
46.9k657107
46.9k657107
add a comment |
add a comment |
$begingroup$
Normally we are looking for an upper bound on the number of operations. In this case there will be $lfloor log_2(X) rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
Normally we are looking for an upper bound on the number of operations. In this case there will be $lfloor log_2(X) rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
Normally we are looking for an upper bound on the number of operations. In this case there will be $lfloor log_2(X) rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
$endgroup$
Normally we are looking for an upper bound on the number of operations. In this case there will be $lfloor log_2(X) rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
answered Jan 17 at 3:35
Ross MillikanRoss Millikan
297k23198371
297k23198371
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3076549%2fbinary-addition-algorithm%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$
It is not clear what you are asking. Please give an example. As for flipping the right-most $0$ and all $1$s following, that gives $X+1$?
$endgroup$
– Daniel Mathias
Jan 17 at 3:24
$begingroup$
Yes, so we start from 0 and increment by 1 n times. I think that's whats happening.
$endgroup$
– Einstein the troll
Jan 17 at 3:27
$begingroup$
Your title refers to addition, but there is no addition in the algorithm. Your algorithm will not work for any $X$ that is not a power of $2$. It will only print a single $1$ followed by some number of zeros.
$endgroup$
– Ross Millikan
Jan 17 at 3:36
$begingroup$
Why would you use such a convoluted algorithm for converting a number to binary?
$endgroup$
– Aditya Dua
Jan 17 at 3:44