How to Perform a Bitwise Group Function

Is it possible to perform a bitwise group function?

MySQL:

SELECT user_id, BIT_OR(permissions) as all_perms
FROM permissions
GROUP BY user_id

Bitwise operation in Group By

Your question just became very interesting.

Create this function(you may want to reconsider the name)

CREATE function f_test
(
  @param bigint
)
  returns @t table (value bigint)
AS
BEGIN

;WITH CTE AS
(
  SELECT
    @param % 2 value, 
    1 multiplier, 
    @param / 2 remain
  UNION ALL
  SELECT
    remain % 2, 
    multiplier * 2,
    remain / 2
  FROM
    CTE
  WHERE
    remain > 0
)
INSERT @t
SELECT multiplier 
FROM CTE
WHERE value = 1
RETURN

END

Now you can run this script, I am using a table variable, replace it with your table:

DECLARE @t table(PermissionId int, BitMask bigint)
INSERT  @t values(1,4),(2,7),(1,8),(1,5)

SELECT
  t1.PermissionId, 
  SUM(distinct t2.Value) Total
FROM
  @t t1
CROSS APPLY
f_test(t1.BitMask) t2
GROUP BY
  t1.PermissionId

Result:

PermissionId  Total
1             13
2             7

Performing a bitwise sum

If all of your test values are single bits as in your example (1, 2, 8) - simply use SUM(DISTINCT col) in your query.

Hope that helps.

(For reference: http://msdn.microsoft.com/en-us/library/ms187810.aspx)

How to use bitwise operations to assign specific bits of a byte according to two other bytes? (bit blend according to a mask)

The standard bithack for this is "Merge bits from two values according to a mask" - I added your variable names for the inputs to the existing comments from Sean Anderson's collection of bithacks.

unsigned int a;    // (ByteToAlter)    value to merge in non-masked bits
unsigned int b;    // (ValuesToAssign) value to merge in masked bits
unsigned int mask; // (BitsToAssign)   1 where bits from b should be selected; 0 where from a.

unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask); 

As the bithack comments note, the straight-forward way is (a & ~mask) | (b & mask) - clear the bits you're not keeping in each input, then OR them together.

How a ^ ((a ^ b) & mask) works:

bitdiff = a^b is the bitwise difference between those inputs.

It has a 1 where they differ, and a 0 where they're the same. (By definition of XOR).

a ^ bitdiff would flip every bit in a that's different from b. In fact, b == a ^ bitdiff.

One way to show that's true is that XOR is associative, so a ^ (a^b) = (a ^ a) ^ b.

And x^x = 0, just like x-x = 0.

0 ^ x = x, so (a^a) ^ b = 0 ^ b = b.

But if we mask the bitdiff to only set bits of a to bits from b at certain positions, we've achieved our goal: bitwise blend according to a mask. blend = a ^ (bitdiff & mask);

---

Special cases of the (a & ~mask) | (b & mask) simple version

If your inputs are arranged so ValuesToAssign only has any 1 bits at positions selected by the mask, you can optimize away the b & mask part, leaving just (a & ~mask) | b. (Eraklon's answer). Clear the unselected bits, then OR in the new values to set any bits that should be set.

A further special case is when ValuesToAssign == BitsToAssign, i.e. the modification only ever sets bits, never clearing them. That's what OR does, so of course this case optimizes to a | b, with no need to clear bits in a before ORing.

---

Efficiency:

r = a ^ ((a ^ b) & mask); is only 3 boolean operations,

vs. 4 for (a & ~mask) | (b & mask) if all three inputs are runtime-variables. (One bitwise NOT, two AND, plus an OR).

If mask is a constant, then constant-propagation into ~mask makes it a constant, and most machines can do AND-immediate with at least an 8-bit AND mask. So you'd still only need 3 instruction: two ANDs (with inverse constants) and an OR.

Some machines (like x86 with BMI1) even have an andn instruction that does x & ~y, allowing the (a & ~mask) | (b & mask) to be done with 3 instructions.

For latency, (a & ~mask) | (b & mask) has more instruction-level parallelism. If mask and ~mask are ready ahead of a and b, there are only two parallel AND operations, and an OR, from a and b inputs being ready to the output being ready. On a normal superscalar machine (that can do two independent AND ops in the same cycle), that's only 2 cycle latency from inputs to outputs. (Again, assuming mask is ready early, or that an instruction like andn exists to do a & ~mask in a single operation).

If the critical path goes through mask (i.e. it's not ready early), and you don't have an instruction like andn to do ~ and & as one operation, the latency from mask to result is 3 operations, ~, &, and |. (Assuming the b & mask can run in parallel without slowing down any of those three).

Latencies for (a & ~mask) | (b & mask) on a modern OoO exec machine.

(Not the same thing as throughput cost)

• a -> result: 2 cycles
• b -> result: 2 cycles
• mask -> result: 3 cycles (or 2 on some machines)

But the bit-difference way doesn't have any ILP; it's a chain of 3 operations. a^b requires both of those inputs to be ready for the first step, then mask needs to be ready for the & mask step. The final a ^ ... step is using inputs that were already needed earlier. So it's only 3 operations, but they're serial.

Latencies for a ^ ((a ^ b) & mask) on a modern OoO exec machine.

• a -> result: 3 cycles
• b -> result: 3 cycles
• mask -> result: 2 cycles

Related Q&As:

• Merge bit sequences a and b according to a mask - this is called a blend in SIMD programming. IDK if anyone else uses the "bit-blend" term I like to use for this operation, but IMO that clearly describes it. x86's AVX-512 extension has a 3-input boolean operation vpternlog with a truth-table from an 8-bit immediate, and thus can do it in a single instruction.

• Swapping bits at a given point between two bytes - The same bithack idea, but applying the masked bit-difference to both inputs to exchange bits at the mask positions.

• https://catonmat.net/low-level-bit-hacks - starts gently with an intro to the operators (like ^ being bitwise XOR). Includes bithacks that use + and - (and the carry propagation effects of hitting a 1 or 0, like x & (x-1) to clear the right-most set bit.)

• https://agner.org/optimize/ for more about tuning for modern CPUs.

How to perform bitwise operations arithmetic in MS-ACCESS

If you can run your query in in ANSI-92 Query Mode (e.g. by changing the Access UI Query Mode or by connecting to it using ADO classic or ADO.NET), use the BAND operator.

The following code sample prints this to the Immediate window:

8 AND 7: -1 
8 BAND 7: 0 

The first case (AND) treats both numbers as True values, so True AND True gives -1 (True). I think the BAND approach is what you're after.

Public Sub BitwiseAndQuery()
    'the db engine treats numbers as booleans with AND '
    Debug.Print "8 AND 7: "; _
        CurrentDb.OpenRecordset("SELECT 8 AND 7")(0)

    'ADO includes BAND for bitwise AND '
    Dim rs As Object
    Set rs = CreateObject("ADODB.Recordset")
    rs.Open "SELECT (8 BAND 7)", CurrentProject.Connection
    Debug.Print "8 BAND 7:"; rs(0)
    rs.Close
    Set rs = Nothing
End Sub

---

Related Topics