32

Given the following table:

CREATE TABLE BitValues ( n int )

Is it possible to compute the bitwise-OR of n for all rows within a subquery? For example, if BitValues contains these 4 rows:

+---+
| n |
+---+
| 1 |
| 2 |
| 4 |
| 3 |
+---+

I would expect the subquery to return 7. Is there a way to do this inline, without creating a UDF?

0

10 Answers 10

15

I see this post is pretty old and there are some useful answers but this is a pretty crazy straight forward method...

Select  
    SUM(DISTINCT(n & 0x01)) +
    SUM(DISTINCT(n & 0x02)) +
    SUM(DISTINCT(n & 0x04))
    as OrN
From BitValues
2
  • 1
    MAX() instead of SUM(distinct()) for each bitwise operation would probably be more efficient (untested) and give the same result. MIN on every bitwise operation would then be like doing an aggregate bitwise-AND. This is still the simplest (and therefore best) method though.
    – Arkaine55
    Aug 5, 2016 at 20:04
  • 2
    Wow! An actual use-case for sum(distinct). Dec 7, 2016 at 14:48
13
WITH    Bits
          AS ( SELECT   1 AS BitMask
               UNION ALL
               SELECT   2
               UNION ALL
               SELECT   4
               UNION ALL
               SELECT   8
               UNION ALL
               SELECT   16
             )
    SELECT  SUM(DISTINCT BitMask)
    FROM    ( SELECT    1 AS n
              UNION ALL
              SELECT    2
              UNION ALL
              SELECT    3
              UNION ALL
              SELECT    4
              UNION ALL
              SELECT    5
              UNION ALL
              SELECT    6
            ) AS t
            JOIN Bits ON t.n & Bits.BitMask > 0
5
  • The execution plan of this one looks a wee bit better than that of @Andomar's solution. Maybe someone who can better decipher execution plans can weigh in.
    – Daniel
    Oct 20, 2010 at 19:13
  • When I ran this and @Andomar's solution in the same batch, it was 44% of the batch.
    – Daniel
    Oct 20, 2010 at 19:15
  • 1
    +1 Although this one supports only 4 bits, it's faster because it does a left semi join without a distinct sort. Edited my query to do the same. Cool. :)
    – Andomar
    Oct 20, 2010 at 19:53
  • @Andomar - I ended up using a blend of your query and his. I up-voted yours. Thanks for your help.
    – Daniel
    Oct 20, 2010 at 19:58
  • 1
    I'm not sure how to use this. I tried adding the values (1,2,4,3) to the CTE on top. It returns 10 instead of 7.
    – jumxozizi
    Oct 7, 2016 at 10:49
11

A simple solution which is a mix of @AlexKuznetsov's and @Andomar's solutions.
The bit mask is generated by a recursive Common Table Expression, but in a simpler way than in @Andomar's solution.
The bits are then summed just like in @AlexKuznetsov's solution.
In this example I assume a 16 bits mask is required, hence the 65536 limit. You can indicate a N-bits mask by changing 65536 to 2^N.

WITH Bits AS
(
    SELECT 1 BitMask
    UNION ALL
    SELECT 2 * BitMask FROM Bits WHERE BitMask < 65536 -- recursion
)
SELECT SUM(DISTINCT BitMask)
FROM
    (SELECT 1 n
    UNION ALL
    SELECT 2 n
    UNION ALL
    SELECT 4 n
    UNION ALL
    SELECT 3 n) t
    INNER JOIN Bits ON t.n & Bits.BitMask > 0
1
  • Very nice solution indeed.
    – mzedeler
    Apr 17, 2013 at 7:32
3

Preparations:

if object_id(N'tempdb..#t', N'U') is not null drop table #t;
create table #t ( n int );
insert into #t values (1), (2), (4), (3);

Solution:

select max(n & 8) + max(n & 4) + max(n & 2) + max(n & 1) from #t;
2
  • i like this despite its limitation that you have to specify the maximum size of bitmask you want to support.
    – Brad
    Oct 24, 2014 at 21:36
  • edit (derp): just realized that the accepted answer does also, this just swaps max(n & [bitvalue]) for the left join to the bitvalue cte.
    – Brad
    Oct 24, 2014 at 21:49
2

You can use a variable and do a "bitwise or" (|) for each row:

declare @t table (n int)
insert @t select 1 union select 2 union select 4

declare @i int
set @i = 0

select  @i = @i | n
from    @t

select @i

This prints 7. Note that assigning variables in a select is not officially supported.

In a more strictly SQL way, you can create a table with one row for each bit. This table would have 31 rows, as the 32nd bit is a negative integer. This example uses a recursive CTE to create that table:

declare @t table (n int)
insert @t select 1 union select 2 union select 3

; with bits(nr, pow) as 
(
    select  1
    ,       1
    union all
    select  nr + 1
    ,       pow * 2
    from    bits
    where   nr <= 30
)
select  sum(b.pow)
from    bits b
where   exists
        (
        select  *
        from    @t t  
        where   b.pow & t.n > 0
        )

This sums the bits where any bit in the source table is set.

6
  • 1
    This isn't inline, within a subquery. I would like the result to be usable from an outer query.
    – Daniel
    Oct 20, 2010 at 18:32
  • @Daniel: You can place this in user defined function (UDF) and use it from an outer query
    – Andomar
    Oct 20, 2010 at 18:40
  • 1
    How to avoid using a UDF is part of the question.
    – Daniel
    Oct 20, 2010 at 18:44
  • @Daniel: You could use the second query with the CTE. It would work, but will be slow. (Consider a CLR aggregate for performance.)
    – Andomar
    Oct 20, 2010 at 18:49
  • @Andomar: I was thinking along those lines but, like you, thought 'exploding' the result set using CROSS JOIN might make it slow.
    – Daniel
    Oct 20, 2010 at 18:55
1

I tried using COALESCE function and it works, example:

DECLARE @nOrTotal INT

SELECT @nOrTotal = COALESCE(@nOrTotal, 0) | nValor 
    FROM (SELECT 1 nValor
              UNION 
          SELECT 2
              UNION 
          SELECT 2) t

SELECT @nOrTotal

>> Result: 3
1
  • 1
    I'm aware of this solution, but the question explicitly states within a subquery.
    – Daniel
    Jul 27, 2012 at 18:32
1

This is an alternative, without WITH (hurrah!!!):

    select sum(distinct isnull(n & BitMask, 0)) as resultvalue
    from 
    (
          SELECT    1 AS n
          UNION ALL
          SELECT    2
          UNION ALL
          SELECT    4
          UNION ALL
          SELECT    3
    ) t
    INNER JOIN (SELECT 0 BitMask union all SELECT 1 union all SELECT 2 union all SELECT 4 union all SELECT 8 union all SELECT 16 union all SELECT 32 union all SELECT 64 union all SELECT 128 union all SELECT 256 union all SELECT 512 union all SELECT 1024 union all SELECT 2048 union all SELECT 4096 union all SELECT 8192 union all SELECT 16384 union all SELECT 32768 union all SELECT 65536) Bits -- = SELECT POWER(2, 16)
    ON n & BitMask = BitMask;

Also consider a Group By example:

 -- Setup temp table to produce an example --
 create table #BitValues
 (
    id int identity(1,1)
    ,value int
    ,groupby varchar(10)
 )

 insert into #BitValues
 SELECT    1 AS value, 'apples'
          UNION ALL
          SELECT    2, 'apples'
          UNION ALL
          SELECT    4, 'apples'
          UNION ALL
          SELECT    3, 'apples'

 -- Bit operation: --
  select groupby, sum(distinct isnull(value & BitMask, 0)) as tempvalue
  from #BitValues
  INNER JOIN (SELECT 0 BitMask union all SELECT 1 union all SELECT 2 union all SELECT 4 union all SELECT 8 union all SELECT 16 union all SELECT 32 union all SELECT 64 union all SELECT 128 union all SELECT 256 union all SELECT 512 union all SELECT 1024 union all SELECT 2048 union all SELECT 4096 union all SELECT 8192 union all SELECT 16384 union all SELECT 32768 union all SELECT 65536) Bits -- = SELECT POWER(2, 16)
      ON value & BitMask = BitMask
  group by groupby

The first example is meant to be slower than WITH. However when you use GroupBy with some other data, the queries are largely the same cost-wise.

Another way to do this is

    select 
    groupby
      ,max(case when n & 1 = 1 then 1 else 0 end)
            +
        max(case when n  & 2 = 2 then 2 else 0 end)
            +
        max(case when n & 4 = 4 then 4 else 0 end)  
            +
        max(case when n & 8 = 8 then 8 else 0 end)
            +
        max(case when n & 16 = 16 then 16 else 0 end)
            +
        max(case when n & 32 = 32 then 32 else 0 end)
            +
        max(case when n & 64 = 64 then 64 else 0 end)
            +
        max(case when n & 128 = 128 then 128 else 0 end)
            +
        max(case when n & 256 = 256 then 256 else 0 end)
            +
        max(case when n & 512 = 512 then 512 else 0 end)
            +
        max(case when n & 1024 = 1024 then 1024 else 0 end)
            as NewDNC
    from #BitValues
    group by groupby;

It's a bit worse because of repetition in code, a bit more readable and similar in execution cost.

0

Are you looking for something like this?

EDIT: As noted in other comments, this answer was based on the assumption that the BitValues table would only contain powers of 2. I tried to read between the lines of the question and infer a use for the inline subquery.

declare @BitValues table (
    n int
)

declare @TestTable table (
    id int identity,
    name char(10),
    BitMappedColumn int
)

insert into @BitValues (n)
    select 1 union all select 2 union all select 4

insert into @TestTable
    (name, BitMappedColumn)
    select 'Joe', 5 union all select 'Bob', 8

select t.id, t.name, t.BitMappedColumn
    from @TestTable t
        inner join (select SUM(n) as BitMask from @BitValues) b
            on t.BitMappedColumn & b.BitMask <> 0
1
  • Not quite, but you gave me an idea. I need all the values OR'd together, not just check some bits.
    – Daniel
    Oct 20, 2010 at 18:36
0

For me that is the best solution.

declare @res int
set @res=0    
SELECT  @res=@res|t.n
    FROM    ( SELECT    1 AS n
              UNION ALL
              SELECT    2
              UNION ALL
              SELECT    3
              UNION ALL
              SELECT    4
              UNION ALL
              SELECT    5
              UNION ALL
              SELECT    6
            ) AS t
-1

Your best bet for a readable and re-usable solution would be to write a a custom CLR Aggregate to perform bitwise or. A tutorial for creating this type of operation can be found here: http://msdn.microsoft.com/en-us/library/91e6taax(VS.80).aspx

1
  • It's a piece of cake to write this in T-SQL as a UDF. I was just trying to avoid writing a single-use function, and thought it seemed like an interesting challenge.
    – Daniel
    Oct 20, 2010 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.