Recursively counting numbers with fixed bit countsI ran across this problem in a reddit side-bar job-ad, and was intrigued by the task (description paraphrased to decrease googleability):
Write a function
uint64_t bitsquares(uint64_t a, uint64_t b);
such that it return the number of integers in [a,b] that have a square number of bits set to 1. Your function should run in less than O(b-a).
I think I see how to do it in something like logarithmic time. Here’s how:
First off, we notice that we can list all the squares between 0 and 64: these are 0, 1, 9, 16, 25, 36, 49, and 64. The function I will propose will run through a binary tree of depth 64, shortcutting through branches whenever it can. In fact; changing implementation language completely, I wonder if I cannot even write it comprehensively in Haskell.
RSS feeds available for 