# Xaprb

Stay curious!

## Tips and tricks for bitwise arithmetic

Bitwise arithmetic can be very useful, and not just for C and graphics programmers, but for all types of programming tasks. Those who use it frequently enough become fluent. Here I present a few tips. As I think of more, I will add them here.

### Signed versus unsigned

Remember numbers can be signed or unsigned. Know the difference, and know the arithmetic for both. For example, when checking to see if a certain bit is set:

```if (number & mask > 0) // wrong!  It could be < 0

### Let the compiler optimize

When you care about performance and want a 1/0 value indicating whether a (compile-time constant) bit is set, don’t write conditional logic. Conditional logic ends up being branches and jumps in the final instruction set, and this is a severe performance hit. Branches and jumps cause the processor to have to speculate about what instructions are in the future, interfering with pipelining and pre-fetching of memory. It might seem trivial, but it’s not; all the memory access can be avoided (huge saving!) and the pipeline can stay full. Instead, write your test like this:

`bitset = (number & bit) / bit;`

Why is this optimal? The compiler is smart enough to recognize you are dividing by a constant multiple of two, and can emit a `shift` instruction, so your actual instruction ends up being very cheap indeed, with no need for branching. If you’re writing it in SQL, this is also much better than using a CASE statement:

```set @bitset = case when @number & @bit <> 0 then 1 else 0 end; -- bad!
set @bitset = (@number & @bit) / @bit; -- good!```

The CASE statement is to be avoided because it’s essentially a function call.

### Switching two values

You can switch two values without a temporary variable by bitwise `XOR`ing them three times, e.g.

```declare @a int, @b int
select @a = 5, @b = 10
set @a = @a ^ @b
set @b = @a ^ @b
set @a = @a ^ @b
select @a, @b```

Or, in MySQL,

```select @a := 5, @b := 10;
select @a := (@a ^ @b);
select @b := (@a ^ @b);
select @a := (@a ^ @b);
select @a, @b;
+------+------+
| @a   | @b   |
+------+------+
| 10   | 5    |
+------+------+```

### Multiply by 1/0 instead of using a conditional

This isn’t strictly bitwise arithmetic, it’s about using the power of true and false. This tip is especially useful in SQL. It comes up often when I’m writing a query to use valid values and ignore invalid ones, especially in updates from a grouped set of data. For example, suppose I want to calculate whether orders are valid in one query, then find the total value of valid orders, total value of all orders, count of items on valid orders, and count of items on all orders in a single query. The first query will be something that ends up setting a 1 or 0 value in a column, something like `update order set valid = 1 where...`. The second query could now look something like the following:

```select
sum(case when o.valid = 1 then i.value else 0 end) as valid_value,
sum(i.value) as valid_value,
sum(case when o.valid = 1 then 1 else 0 end) as valid_items,
count(*) as total_items
from orders as o
inner join ordered_items as i on i.order = o.order_id
group by o.order_id```

All those `case when` statements are inefficient and hard to read, write, debug and maintain. The following is much simpler:

```select
sum(o.valid = 1 * i.value) as valid_value,
sum(i.value) as total_value,
sum(i.value) as valid_items,
count(*) as total_items
from orders as o
inner join ordered_items as i on i.order = o.order_id
group by o.order_id```

To negate the logic, use bitwise `XOR`. For example, suppose I have a table of aggregated sales data that’s over-normalized to include a 1/0 flag in the primary key:

```create table salesdata (
day date not null,
is_catalog tinyint not null,
orders int not null,
sales decimal(12,2) not null,
primary key(day, is_catalog_sale)
);```

I want to de-normalize this data and end up with the following structure:

```create table salesdata_denormalized (
day date not null,
non_catalog_orders int not null,
non_catalog_sales decimal(12,2) not null,
catalog_orders int not null,
catalog_sales decimal(12,2) not null,
primary key(day)
);```

The following query will do it efficiently and compactly:

```insert into salesdata_denormalized
(day, non_catalog_orders, non_catalog_sales, catalog_orders, catalog_sales)
select
day,
sum(orders * (is_catalog ^ 1)),
sum(sales * (is_catalog ^ 1)),
sum(orders * is_catalog),
sum(sales * is_catalog)
from salesdata
group by day;```

Written by Xaprb

September 28th, 2005 at 4:04 pm

Posted in Uncategorized

### 8 Responses to 'Tips and tricks for bitwise arithmetic'

1. It should be noted that “if (number & mask != 0)” is merely “confusing, Bad practice!” only if mask represent a single bit of mutually exclusive flags.

If “mask” can have several bits set, then it’s just plain wrong.

James Curran

26 Feb 07 at 1:18 pm

2. set @bitset = case when @number & @bit 0 then 1 else 0 end; â€” bad!
set @bitset = (@number & @bit) / @bit; â€” good!

could these also be written as

set @bitset = ((@number & @bit) = @bit); â€” better? we avoid an expensive division.

Is there any particular reason for the division?

salman

15 Feb 08 at 6:09 pm

3. i would wish you would write the following line

sum(o.valid = 1 * i.value) as valid_value,

as

sum((o.valid = 1) * i.value) as valid_value,

because for some programming lang ‘*’
has greater precedence than ‘=’.
the expression becomes

sum(o.valid = (1 * i.value)) as valid_value,
it just seems confusing.

P.S. if i put my foot in mouth, just give me a shout.

salman

15 Feb 08 at 6:14 pm

4. by the way nice article.

salman

15 Feb 08 at 6:14 pm

5. [...] the permissions increase in powers of 2.Â  i’ll not go into why this works, since it’s covered elsewhere, but sufficed to say that bitwise, each number is distinct and non-inclusive of the other [...]

450AHX

5 Jun 09 at 5:21 pm

7. Good article. It’s nice to someone moving beyond the simple storing and retrieving bits using masks.

Mike

24 Dec 09 at 12:31 pm

8. I think using bitwise operation confusing and should be avoided if you and your colleagues don’t have an assembler base!

nerkn

13 Jul 10 at 11:47 am