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:

n	f(n)
0	1
1	2
2	1
3	4
4	1
5	2
6	1
7	8

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

n	f(n)
1	1
2	2
3	1
4	4
5	1
6	2
7	1
8	8

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
1	1024
2	512
4	256
8	128
16	64
32	32
64	16
128	8
256	4
512	2
1024	1

She is one of a kind, eh?