Here are 3 good places to find bit manipulation hacks and efficient low level algorithms for various mathematical functions:
Bit Twiddling Hacks (Stanford)
The Aggregate Magic Algorithms (University of Kentucky)
HAKMEM (MIT)
If you have other ones like this, do not hesitate to post them in the comments !
Bit hacks and low level algorithms
Subscribe to:
Post Comments (Atom)
April 30, 2010 at 10:46 AM
Hi,
you can try (if you dont already) the well-known book "Hackers Delight": http://www.hackersdelight.org/
It has tons of hacks for bit manipulation.
Regards,
Ruben Penalva
http://www.rpenalva.com
May 1, 2010 at 3:01 PM
Thanks for the reference, I did not know it !
May 2, 2010 at 1:54 PM
That's a great post! I knew only the first link.
June 10, 2010 at 7:59 AM
There are a few more tricks that I never found on those pages.
I even sent a mail to the owner of the Bit Twiddling Hack but got no response.
Anyway, here is one trick I really enjoy :
To normalize a number of n-bit range to m-bit range (with m > n)
-> Copy the MSBs to the missing LSBs.
Mathematically it is the same as doing :
(Value * (2^m)-1)/((2^n)-1)
So conversion from 5 bit to 8 bit or 16 bit is very easy and correct. Very usefull for signal processing and image processing.
Ex.
ABCD.E (5 bit) -> ABCD.EABC (8 bit) / ABCD.EABC.DEAB.CDEA (16 bit)
Enjoy.
PS : Please do not hesitate to contact me if you want to discuss the subject.
June 10, 2010 at 12:40 PM
Hey, Thanks you for this nice trick !