Fastest method to get positions of all the 'On' bits
in [General Programming]
|
Prev: zero damenbekleidung bestellen damenbekleidung bestellen uebergroesse only damenbekleidung bestellen damenkleidung kaufen grosse
Next: A question about a programming idiom I see a lot of times.
From: mirza2m on 16 Jul 2008 17:45 Hi, http://en.wikipedia.org/wiki/Hamming_weight has an efficient method to count all the ('on') 1 bits is there a similar way to get the positions of bits that are turned on. Thank you
From: Bartc on 16 Jul 2008 19:21 "mirza2m" <babar.ansari(a)gmail.com> wrote in message news:d28c2213-26cf-46f4-ae60-1889f3578636(a)34g2000hsh.googlegroups.com... > Hi, > http://en.wikipedia.org/wiki/Hamming_weight has an efficient method > to count all the ('on') 1 bits is there a similar way to get the > positions of bits that are turned on. What result do you expect from, say, 0xFFFFFFFF? The numbers 0 to 31, plus a count? But if you have the memory, and can work with 8 or 16 bits at a time, just use the value as an index into a table, each element of which points to a count followed by 0 to 16 position bytes. So value 11 (1011B) will point to: 3, 0,1,3 Estimated table size for 16-bit input values, around 600KB. -- Bart
From: Dann Corbit on 17 Jul 2008 15:24 "mirza2m" <babar.ansari(a)gmail.com> wrote in message news:d28c2213-26cf-46f4-ae60-1889f3578636(a)34g2000hsh.googlegroups.com... > Hi, > http://en.wikipedia.org/wiki/Hamming_weight has an efficient method > to count all the ('on') 1 bits is there a similar way to get the > positions of bits that are turned on. http://chessprogramming.wikispaces.com/bit-twiddling ** Posted from http://www.teranews.com **
From: Moi on 17 Jul 2008 18:27 On Wed, 16 Jul 2008 14:45:31 -0700, mirza2m wrote: > Hi, > http://en.wikipedia.org/wiki/Hamming_weight has an efficient method > to count all the ('on') 1 bits is there a similar way to get the > positions of bits that are turned on. > > Thank you For counting: check the Stanford pages. For iterating: man ffs/ffsl/ ffsll HTH, AvK
From: mirza2m on 18 Jul 2008 12:57
On Jul 16, 4:45 pm, mirza2m <babar.ans...(a)gmail.com> wrote: > Hi, > http://en.wikipedia.org/wiki/Hamming_weighthas an efficient method > to count all the ('on') 1 bits is there a similar way to get the > positions of bits that are turned on. > > Thank you Hi, Thank you for all your replies. This is what I have. Seems to be 4 times faster than the straight forward approach. Only looks at 1 bits. Uses lots of memory may be using http://chessprogramming.wikispaces.com/Bitscan would be a better idea C# private static byte[] log2 = new byte[65536 ]; for (int i = 0; i < 16; i++) log2[(int)Math.Pow(2.0, (double)i)] =(byte) i; /// <summary> /// Finds the number of bits in the parameter. /// </summary> static private List<int> BitPosSparce(int number) { int last = 0; int powOf2 = 0; List<int> pos = new List<int>(); while (number != 0) { last = number; number &= (number - 1); powOf2 = last ^ number; if (powOf2 < 65536) pos.Add( log2[powOf2]); else pos.Add( log2[powOf2 >> 16] + 16); } return pos; } |