Least and most significant bit calculation using bitwise operations
$begingroup$
I am working on a project and I need to calculate the least significant bit (LSB) and most significant bit (MSB) of integers.
Suppose $x$ is an $n$-bit unsigned integer ($n=16, 32$ or $64$). We know that $y=x & ($~$x+1)$ clears all the bits of $x$ except for the LSB. This is lightning fast, just three operations. Is there something similar for the MSB? What is the fastest way to compute it?
discrete-mathematics binary
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
$endgroup$
|
show 7 more comments
$begingroup$
I am working on a project and I need to calculate the least significant bit (LSB) and most significant bit (MSB) of integers.
Suppose $x$ is an $n$-bit unsigned integer ($n=16, 32$ or $64$). We know that $y=x & ($~$x+1)$ clears all the bits of $x$ except for the LSB. This is lightning fast, just three operations. Is there something similar for the MSB? What is the fastest way to compute it?
discrete-mathematics binary
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
$endgroup$
1
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
1
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
1
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06
|
show 7 more comments
$begingroup$
I am working on a project and I need to calculate the least significant bit (LSB) and most significant bit (MSB) of integers.
Suppose $x$ is an $n$-bit unsigned integer ($n=16, 32$ or $64$). We know that $y=x & ($~$x+1)$ clears all the bits of $x$ except for the LSB. This is lightning fast, just three operations. Is there something similar for the MSB? What is the fastest way to compute it?
discrete-mathematics binary
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
$endgroup$
I am working on a project and I need to calculate the least significant bit (LSB) and most significant bit (MSB) of integers.
Suppose $x$ is an $n$-bit unsigned integer ($n=16, 32$ or $64$). We know that $y=x & ($~$x+1)$ clears all the bits of $x$ except for the LSB. This is lightning fast, just three operations. Is there something similar for the MSB? What is the fastest way to compute it?
discrete-mathematics binary
discrete-mathematics binary
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
edited Jan 11 at 5:56
Eric Wofsey
183k13209337
183k13209337
asked Dec 6 '18 at 8:32
plus1plus1
3911
asked Dec 6 '18 at 8:32
plus1plus1
3911
asked Dec 6 '18 at 8:32
plus1plus1
3911
3911
1
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
1
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
1
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06
|
show 7 more comments
1
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
1
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
1
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06
1
1
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
1
1
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
1
1
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06
|
show 7 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Here is a way that works in $log(|n|)$ where |n| is the number of bits needed to represent $n$.
Let's say we have a 32-bit integers.
MST(int x)
{
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x++;
x>>=1;
return x;
}
The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
$endgroup$
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
add a comment |
$begingroup$
I just came across this hack from an old book about chess programming:
$$
y=XOR(x,x-1)=00...001111...11,
$$
where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.
answered Dec 17 '18 at 14:17
plus1plus1
3911
$endgroup$
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
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%2f3028227%2fleast-and-most-significant-bit-calculation-using-bitwise-operations%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$
Here is a way that works in $log(|n|)$ where |n| is the number of bits needed to represent $n$.
Let's say we have a 32-bit integers.
MST(int x)
{
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x++;
x>>=1;
return x;
}
The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
$endgroup$
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
add a comment |
$begingroup$
Here is a way that works in $log(|n|)$ where |n| is the number of bits needed to represent $n$.
Let's say we have a 32-bit integers.
MST(int x)
{
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x++;
x>>=1;
return x;
}
The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
$endgroup$
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
add a comment |
$begingroup$
Here is a way that works in $log(|n|)$ where |n| is the number of bits needed to represent $n$.
Let's say we have a 32-bit integers.
MST(int x)
{
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x++;
x>>=1;
return x;
}
The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
$endgroup$
Here is a way that works in $log(|n|)$ where |n| is the number of bits needed to represent $n$.
Let's say we have a 32-bit integers.
MST(int x)
{
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x++;
x>>=1;
return x;
}
The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
edited Dec 15 '18 at 10:49
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
answered Dec 12 '18 at 10:00
narek Bojikiannarek Bojikian
30618
30618
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
add a comment |
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
1
1
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
With the obvious generalization for 64-bit I guess..
$endgroup$
– plus1
Dec 14 '18 at 20:26
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
$begingroup$
You’re right we only add the line “x|=(x>>32)”
$endgroup$
– narek Bojikian
Dec 15 '18 at 10:50
add a comment |
$begingroup$
I just came across this hack from an old book about chess programming:
$$
y=XOR(x,x-1)=00...001111...11,
$$
where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.
answered Dec 17 '18 at 14:17
plus1plus1
3911
$endgroup$
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
add a comment |
$begingroup$
I just came across this hack from an old book about chess programming:
$$
y=XOR(x,x-1)=00...001111...11,
$$
where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.
answered Dec 17 '18 at 14:17
plus1plus1
3911
$endgroup$
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
add a comment |
$begingroup$
I just came across this hack from an old book about chess programming:
$$
y=XOR(x,x-1)=00...001111...11,
$$
where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.
answered Dec 17 '18 at 14:17
plus1plus1
3911
$endgroup$
I just came across this hack from an old book about chess programming:
$$
y=XOR(x,x-1)=00...001111...11,
$$
where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.
answered Dec 17 '18 at 14:17
plus1plus1
3911
answered Dec 17 '18 at 14:17
plus1plus1
3911
answered Dec 17 '18 at 14:17
plus1plus1
3911
answered Dec 17 '18 at 14:17
plus1plus1
3911
3911
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
add a comment |
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
1
1
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
$begingroup$
Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!!
$endgroup$
– plus1
Dec 19 '18 at 6:44
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%2f3028227%2fleast-and-most-significant-bit-calculation-using-bitwise-operations%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
1
$begingroup$
If $x=2$, then $x & (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 9:29
1
$begingroup$
@Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it.
$endgroup$
– plus1
Dec 6 '18 at 10:48
$begingroup$
Have a look at this related SO post.
$endgroup$
– Axel Kemper
Dec 6 '18 at 13:14
$begingroup$
You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $&$ does not distribute over $+$. Again, if $x=2$ then $x&(sim x + 1) = 2$.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:02
1
$begingroup$
Usually to extract a bit at a particular location we use a `bit mask' with a one in the location that needs to be extracted.
$endgroup$
– Daniel Beale
Dec 6 '18 at 15:06