# What is this bitfield thing?

An array of true/false values. Usually a fixed-size array, due to platform constraints. Also a very compact array – taking exactly one bit to store each element. In other words: a boolean vector or set.

# So does anyone use it?

Plenty of usage around, many of it inherited from history. Probably the most known bitfield is the POSIX access mode field, used by every filesystem on your UNIX-like OS:

```
$ LC_ALL=C ls -l /etc/passwd
-rw-r--r-- 1 root root 2473 Sep 1 2016 /etc/passwd
```

# What?

I’m talking about this field where dashes mix with letters. It shows me that this file is readable and writable by its owner (first triplet after the initial dash: `rw-`

), readable by its group (second triplet: `r--`

) and also readable by other users (last triplet: `r--`

). The first blank is used for displaying any special bits. Underneath this representation lies a bitfield:

Flag | Octal value | Purpose |
---|---|---|

S_ISUID | 04000 | Set user ID on execution |

S_ISGID | 02000 | Set group ID on execution |

S_ISVTX | 01000 | Sticky bit |

S_IRUSR, S_IREAD | 00400 | Read by owner |

S_IWUSR, S_IWRITE | 00200 | Write by owner |

S_IXUSR, S_IEXEC | 00100 | Execute/search by owner |

S_IRGRP | 00040 | Read by group |

S_IWGRP | 00020 | Write by group |

S_IXGRP | 00010 | Execute/search by group |

S_IROTH | 00004 | Read by others |

S_IWOTH | 00002 | Write by others |

S_IXOTH | 00001 | Execute/search by others |

# How do your strange numbers work? Why do you use only 0, 1, 2 and 4?

Let’s look at bits grouped into threes (BTW: conveniently 2³ = 8 and *octo* is Latin for ‘eight’ – hence *octal*, also the number of legs on GitHub’s *octocat*).

```
000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7
```

We’re using these digits from 0 to 7 to represent such groups. If we expand 644 to ones and zeros by substituting from the above table, we get `110 100 100`

(does it look familiar already?). Also, notice that for 1, 2 and 4 exactly one bit is set, each time in a different location.
Adding together numbers which contain only zeros and exactly one of these three digits, at any position, will never carry (increment other columns). This is because 4 + 2 + 1 = 7, the maximum digit at any position. Now, let’s calculate the bitfield again:

field | value |
---|---|

S_IRUSR | 00400 |

S_IWUSR | 00200 |

S_IRGRP | 00040 |

S_IROTH | 00004 |

Σ | 00644 |

There, a quick primer on octal numbers.

# And how does this translate to `-rw-r--r--`

again?

Start with the `S_IRUSR`

bit position. Output a dash if bit is unset, otherwise output a letter matching the bit’s intent (`r`

for read – an octal 4, `w`

for write = 2, `x`

for execute = 1). The leading dash is for some additional bits that we’re not going to cover here. Doing that for all eight possible combinations results in this table:

```
000 = 0 = ---
001 = 1 = --x
010 = 2 = -w-
011 = 3 = -wx
100 = 4 = r--
101 = 5 = r-x
110 = 6 = rw-
111 = 7 = rwx
```

Other popular values used here are 600, 400 and 777. See if you can figure out what they mean.

# You said it’s an array

It’s a compact representation of one. Let’s convert an array to bits, holding on to our filesystem permissions example.

```
irb> perms = [false, false, false, # special bits
true, true, false, # owner
true, false, false, # group
true, false, false] # others
irb> perms.inject(0) { |acc, bit| acc << 1 | (bit ? 1 : 0) }
=> 420
```

# That’s not 644

IRb gave us the answer in decimal notation. Let’s ask it for octal again.

```
irb> 420.to_s(8)
644
```

Or binary even

```
irb> 420.to_s(2)
=> "110100100" # Looks familiar?
```

# Okay. And how do I decode the number?

```
irb> 0o644.to_s(2).rjust(12, "0").each_char.map { |b| b.to_i == 1 }
=> [false, false, false, true, true, false, true, false, false, true, false, false]
```

Ruby even gives us these bits (in MSB-first-order – starting from the rightmost one) when indexing an integer. Less magic involved.

```
irb> (0...12).reverse_each.map { |i| 0o644[i] == 1 }
=> [false, false, false, true, true, false, true, false, false, true, false, false]
```

Prefixing numbers with `0o`

is a common notation for octals. I’m left padding the string to 12 characters with zeros here to output the unset special bits flags.

# And why would I want to use that? Seems complicated

Whenever you have a large number of boolean values, and don’t want to waste storage. This was obviously more relevant in the olden days of tight memory constraints, but still is when programming microcontroller and embedded systems. Not so much on modern hardware, though. If you can use Ruby, you probably don’t have constraints forcing you to use bitfields.

Another use is when you need to compactly represent a set, where allowed values come from a small list. By assigning a single bit to each permitted value, and using its status to signal presence, you can fit up to 64 set members in a single register. (How many members does a set represented by `0644`

have?)

It’s also very efficient in terms of memory access – the processor only needs to fetch one location to work on all of these flags, and compilers are very good at optimizing such access. Therefore you will see it used often in kernel code, memory management, network protocols and games.

I have worked on a large legacy application, where the godobject contains a state machine utilizing many booleans. Instead of having a `TINYINT(1)`

field for each of these, resulting in a table with over 50 columns, all of them are stashed into two 32-bit wide bitfields. Given a million records in the table, the overhead of storing each of them separately was negligible when it was designed, and is definitely negligible today. But it does have the advantage of being less cluttered and easier to understand.

# Do other languages use these?

Certainly. Rust has a nice crate for that:

```
#[macro_use]
extern crate bitflags;
bitflags! {
struct Flags: u32 {
const A = 0b00000001;
const B = 0b00000010;
const C = 0b00000100;
const ABC = Self::A.bits | Self::B.bits | Self::C.bits;
}
}
fn main() {
let e1 = Flags::A | Flags::C;
let e2 = Flags::B | Flags::C;
assert_eq!((e1 | e2), Flags::ABC); // union
assert_eq!((e1 & e2), Flags::C); // intersection
assert_eq!((e1 - e2), Flags::A); // set difference
assert_eq!(!e2, Flags::A); // set complement
}
```

Historically, C programmers usually defined constants plus accessor macros. An excerpt from Linux code linked above, mind the octal notation again, this time represented with a leading zero:

```
#define S_IFMT 0170000
#define S_IFLNK 0120000
#define S_IFREG 0100000
#define S_IFDIR 0040000
#define S_IFCHR 0020000
#define S_IFIFO 0010000
#define S_ISUID 0004000
#define S_ISGID 0002000
#define S_ISVTX 0001000
#define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
#define S_ISREG(m) (((m) & S_IFMT) == S_IFREG)
#define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR)
```

The first one is a mask for extracting only the relevant bits (bits 13-16 counting from LSB), others are bitfield values.

Modern C has storage specifiers for struct fields. You’d declare a struct type for the permissions field, and for each single permission declare it with a bit length of one. Your compiler will then squish them together as efficiently as possible, preserving order. Then just access it like any other struct member.

```
struct posix_perm {
unsigned irusr:1;
unsigned iwusr:1;
unsigned ixusr:1;
unsigned irgrp:1;
unsigned iwgrp:1;
unsigned ixgrp:1;
unsigned iroth:1;
unsigned iwoth:1;
unsigned ixoth:1;
}
```

Rob Pike, designer of Go hates these C bitfields and there is no built-in support, though people have created packages for that.

Erlang and Elixir have a similar concept, and a package to work with them.

# Okay, show me how to work with these in a Ruby project. I’m feeling adventurous

Let’s start with Sequel. There’s a battle-tested plugin for it.

```
class MyModel < Sequel::Model
plugin :bit_fields, :status_bits, [ :started, :finished, :reviewed ]
end
```

In migrations you’d use a `Bignum`

(64 bit) column by default, though it will tolerate longer and shorter columns.

```
Sequel.migration do
change do
alter_table :my_models do
add_column :status_bits, Bignum, :default => 0, :null => false
end
end
end
```

Then you just use the declared bitfield names as if they were regular boolean fields, with some extra features such as scopes.

```
model = MyModel.create
model.started? # => false
model.started = true
model.started? # => true
model.status_bits # => 1
model.finished? # => false
model.finished = true
model.finished? # => true
model.status_bits # => 3
# let's find all the finished instances
MyModel.finished(true).all
# let's find all unfinished instances
MyModel.finished(false).all
# let's find all the started and the finished instances
MyModel.started.finished.all
```

These field lookups are translated to bitwise operations. The last line may translate to a query like:

```
SELECT * from `my_models` WHERE (`status_bits` & 1 == 1) AND (`status_bits` & 2 == 2)
```

# Aha, I see how it’s using these specially bit-positioned numbers. But why the `&`

?

That is bitwise `AND`

. It works by treating the right argument as a mask, and returning only bits from left argument for which 1 was set in the mask. All other bits will be unset. The only two options from `x & 2`

are either `0`

or `2`

, and by comparing we know whether it’s set or unset.

# Clever. How do I set a single bit?

```
model.finished = true; model.save
```

```
UPDATE `my_models` SET `status_bits` = `status_bits` | 2 WHERE id = 424242
```

This is a bitwise `OR`

, which modifies its left argument by setting bits specified by the right argument; regardless if they were set or not.

# And unset?

```
model.finished = false; model.save
```

```
UPDATE `my_models` SET `status_bits` = `status_bits` & ~2 WHERE id = 424242
```

Actually, this plugin would just calculate the new value and set it directly. The above does a mask again, but this time with a *one’s complement* of value 2. This is just the value with all bits flipped. This will keep values at all other bits unchanged, but set a zero at this one.

# What is this Sequel thing, give me the ActiveRecord version

The most popular analog for ActiveRecord is `bitfields`

. It’s really similar:

```
class User < ActiveRecord::Base
include Bitfields
bitfield :my_bits, 1 => :seller, 2 => :insane, 4 => :sensible
end
```

And for migrations:

```
t.integer :my_bits, default: 0, null: false
# OR
add_column :users, :my_bits, :integer, default: 0, null: false
```

New attributes and scopes work almost like the Sequel version. One difference is that scope methods don’t accept a boolean param to search for that flag set or unset. Rather, the unset version is in a separate scope, prefixed with `not_`

.

# So how many of these attributes can I fit in a single bitfield?

Typically up to 64. The Sequel example above does not explicitly assign numeric values to specific attributes (it certainly supports that), while the ActiveRecord one does. Let’s consider how the required numbers work:

```
bitfield :my_bits,
1 => :seller,
2 => :insane,
4 => :sensible,
# ...
128 => :manipulative
# ...
1048576 => :closed_on_wednesdays # That's the 21st flag
2097152 => :closed_on_thursdays
# ...
4294967296 => :likes_muffins # 31st
# ...
```

What’s the last number needed for all 64 flags? And for 500 flags? Generally this is only feasible for small, easily comprehended numbers of flags.

# Is there native database support for this?

PostgreSQL has bit strings, since basically forever. These match what we are doing here very well, with some additional semantics.

Binary strings are different, designed to be more like regular strings but with arbitrary binary data. But you can use `get_bit`

and `set_bit`

functions on them to get more or less the same behavior.

MySQL has BIT as well, matching the PostgreSQL counterpart. It also has SET, which describes a set containing predefined values, but is a bitfield underneath. Presentation is done with a comma-separated string, while any math and aggregation is numeric.

But none of the two plugins above work with any of these. That’s because they target the lowest common denominator, which is bitwise operations on integers – available everywhere.