Puzzle: Fast Bit Counting Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer? Source: Commonly asked in job interviews for Software Engineers. I first heard it in 1996 when I was a graduate student. Solution: This article presents six solutions to this problem. Source code in C is available. 1.
Read full article from Puzzle: Fast Bit Counting
No comments:
Post a Comment