Author |
Topic: Least significant set bit in O(1) time (Read 1568 times) |
|
programmer
Newbie
Posts: 32
|
 |
Least significant set bit in O(1) time
« on: Oct 31st, 2008, 2:43am » |
 Quote  Modify
|
Can we compute the position of least / most significant set bit in a given number in O(1) time??
eg. for input 13, least set bit is the LSB n the highest set bit is MSB
for 6, least set bit is bit 2 (from LSB side wd LSB as bit 1) & highest set bit is bit 3.
|
| « Last Edit: Oct 31st, 2008, 2:43am by programmer » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Least significant set bit in O(1) time
« Reply #1 on: Oct 31st, 2008, 3:42am » |
Quote Modify
|
Adapted from http://graphics.stanford.edu/~seander/bithacks.html
MSSB:
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
// v |= v >> 32; /* for 64 bit */
count_bits(v);
LSSB (except for v=0):
v |= v << 1;
v |= v << 2;
v |= v << 4;
v |= v << 8;
v |= v << 16;
// v |= v << 32; /* for 64 bit */
count_bits(~v)+1;
count_bits (for 32 bits):
c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;
I'm fairly confident this isn't the best solution there is (at very least the counting function can be improved on, see link), but I can't remember, or think of, a better one at the moment.
|
| « Last Edit: Oct 31st, 2008, 3:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Least significant set bit in O(1) time
« Reply #2 on: Oct 31st, 2008, 4:09am » |
Quote Modify
|
LSB:
int lsb=0, v = input;
if( v&0xFFFF==0 ) v>>=16, lsb+=16;
if( v&0xFF==0 ) v>>=8, lsb+=8;
if( v&0xF==0 ) v>>=4, lsb+=4;
if( v&0x3==0 ) v>>=2, lsb+=2;
if( v&0x1==0 ) v>>=1, lsb+=1;
Something similar can be done for MSB.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Least significant set bit in O(1) time
« Reply #3 on: Oct 31st, 2008, 4:17am » |
Quote Modify
|
An interesting one from the same page as before:
Quote:Count the consecutive zero bits (trailing) on the right with modulus division and lookup
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37]; |
|
just add 1. Because LSSB is the number of trailing 0's plus 1.
(And it'd be nice to know what to return if there isn't any set bit, and hence no most or least significant set bit)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
QuantumAnenome
Newbie
Posts: 2
|
|
Re: Least significant set bit in O(1) time
« Reply #4 on: Nov 4th, 2008, 2:01pm » |
Quote Modify
|
This is not a O(1) solution, but a O(log(n)) solution.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Least significant set bit in O(1) time
« Reply #5 on: Nov 4th, 2008, 2:30pm » |
Quote Modify
|
on Nov 4th, 2008, 2:01pm, QuantumAnenome wrote:| This is not a O(1) solution, but a O(log(n)) solution. |
|
It's a fixed number of operations given a processor, so it's O(1).
Besides, there wouldn't be an answer at all if you measured it as you do.
And which of the solution does "this" refer to anyway?
|
| « Last Edit: Nov 4th, 2008, 2:32pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
VincentLascaux
Newbie
Posts: 12
|
|
Re: Least significant set bit in O(1) time
« Reply #6 on: Nov 4th, 2008, 11:32pm » |
Quote Modify
|
on Nov 4th, 2008, 2:30pm, towr wrote:
It's a fixed number of operations given a processor, so it's O(1). |
|
O(1) as a function of what variable?
The original problem is to "compute the position of least / most significant set bit in a given number in O(1) time", I think the only reasonable meaning of this is "compute the position of least / most significant set bit in a given n bit number in O(1) time (considering the complexity as a function of n)"
Then I say such a solution doesn't exist since in the worst case scenario, n bits have to be looked at to figure out that all the bits are 0.
Now if the problem is "Compute the position of least / most significant set bit in a given 32 bit number in O(1) time", I would argue that it doesn't make mathematical sense (saying that the complexity is in O(1) means that the complexity is a function of something, what is that something?)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Least significant set bit in O(1) time
« Reply #7 on: Nov 5th, 2008, 1:01am » |
Quote Modify
|
on Nov 4th, 2008, 11:32pm, VincentLascaux wrote:| (saying that the complexity is in O(1) means that the complexity is a function of something, what is that something?) |
|
If it's O(1), then it's independent of "something", so it doesn't matter what that something is.
f(x)=1 doesn't depend on x, but it's still a function.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Least significant set bit in O(1) time
« Reply #8 on: Nov 5th, 2008, 1:36am » |
Quote Modify
|
It is true that in my solution the number of operations depends on the size of an integer. Strictly speaking, the number of operation is O(log n) where n is the number of bits in an integer.
The "mod 37" approach does not have this problem.
If you consider the number of bits irrelevant, because it is constant, then a simple loop from 0 to 31 (a fixed value) will find the first/last bit in O(1).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Least significant set bit in O(1) time
« Reply #9 on: Nov 5th, 2008, 1:43am » |
Quote Modify
|
on Nov 5th, 2008, 1:36am, Grimbal wrote:| The "mod 37" approach does not have this problem. |
|
It does have the problem that the look-up table, and the modulus have to be changed for larger numbers.
For 64 bits, you can use mod 67; and I'm fairly sure there's similar solutions for more bits. And you need a look-up table at least the size of the number of bits.
However the number of operations does remain the same.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Least significant set bit in O(1) time
« Reply #10 on: Nov 10th, 2008, 11:59pm » |
Quote Modify
|
| hidden: | float x= log 2 n - (int)log 2 n;
if(x > 0)
{
n = n & (n-1);
}
lsb position = log2 n;
msb position = (int)log 2 n; |
|
|
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Least significant set bit in O(1) time
« Reply #11 on: Mar 29th, 2010, 9:28pm » |
Quote Modify
|
did not read all the above but log2(n&~(n-1)) should give the result i guess
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print