One (binary sensation)

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:

nf(n)
01
12
21
34
41
52
61
78

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
nf(n)
11
22
31
44
51
62
71
88

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)]
f(n)Instances
11024
2512
4256
8128
1664
3232
6416
1288
2564
5122
10241

She is one of a kind, eh?

Leave a Reply

Your email address will not be published. Required fields are marked *