It’s not often that bit-twiddling and SQL sit well together. Different sides of the railway line and all that. However, I recently came across an interesting expression which fits the bill:
f(n) = ~n & ~(n-1)
Or in something closer to English:
f(n) = NOT n AND (NOT (n - 1))
This had me scratching my head, because while it was recognisable as something involving bit patterns, I couldn’t immediately make sense of it, even after listing out some values which made it clear that it only emits powers of two:
select n = number , [f(n)] = ~number & ~(~number - 1) from master..spt_values where type='p' and number < 2047
Here are the first few results:
So what is the pattern here? I remained mystified until I came across Hacker’s Delight, which is indeed delightful and kicks off with a collection of very similar expressions. My brain was evaporating after a few pages, but fortunately not before I saw the pattern. Turns out that what I was looking at is the zero-based version of something that is more obvious when one-based, namely “return a mask representing the least significant bit set in the number N”. With the 1 offset applied, we get:
select n = number + 1 , [f(n)] = ~number & ~(~number - 1) from master..spt_values where type='p' and number < 2047
Let’s think about it differently. For an ordered set of bit flags (ordered backwards in this case), this is a window function returning the first member with a given value. We’re getting into more familiar territory here. And the SQL connection runs deeper still: this expression shows up in various SQLOS methods.
However, my favourite discovery was this very eloquent picture of distribution of f(n) for the first 2^m – 1 values of n:
select [f(n)], Instances = count(*) from ( select n = number , [f(n)] = ~number & ~(~number - 1) from master..spt_values where type='p' and number < 2047 ) x group by [f(n)] order by [f(n)]
She is one of a kind, eh?