1 Bitwise Boolean operators

Every programming language you’re likely to encounter has a set of bitwise Boolean operators that can be combined to perform various tasks. These treat the integer datatype in the language in question as an array or list of bits called a bitvetor and allow you to manipulate them directly.

Operator	Meaning	Example
`~`	Bitwise not ( $\lnot$ )	`~` 1100₂ → 1…1110011₂ (i.e., `(~12) == -13`)
`\|`	Bitwise or ( $\lor$ )	1100₂ `\|` 0110₂ → 1110₂ (i.e., `(12 \| 6) == 14`)
`&`	Bitwise and ( $\land$ )	1100₂ `&` 0110₂ → 0100₂ (i.e., `(12 \| 6) == 4`)
`^`	Bitwise xor ( $⊕$ )	1100₂ `^` 0110₂ → 1010₂ (i.e., `(12 ^ 6) == 10`)
`>>`	Bit shift to the right	1101001₂ `>>` 3 → 1101₂ (i.e., `(105 >> 3) == 13`)
`<<`	Bit shift to the left	1101₂ `<<` 3 → 1101000₂ (i.e., `(13 << 3) == 104`)

When shifting, bits that no longer fit within the number are dropped and new bits are dded to keep the number the same number of bits. For left shifts those new bits are always 0s. For right shifts they are sometimes 0s and sometimes copies of whatever bit had been in the highest-order spot before the shift. Copying the high-order bit is called sign-extending because it keeps negative numbers negative in two’s-complement. Which kind of right-shift is performed varies by language and by datatype shifted¹¹ Languages without unsigned types, like Python and Javascript, use >> for sign-extending shifts and >>> for zero-extending shifts. C does not have a >>> operator., with sign-extending shifts for signed integer types and zero-extending shifts for unsigned integer types.

The following code makes use of C’s sign- and zero-exention rules.

// char is an 8-bit integer datatype
signed char x =    0b10100101;
unsigned char y =  0b10100101;
assert((x>>2) == 0b11101001);
assert((y>>2) == 0b00101001);

// short is a 16-bit integer datatype
signed short z =           0b10100101;
assert((z>>2) == 0b0000000000101001);

2 Masks

A bit mask or simply mask is a value used to select a set of bits from another value. Typically, these have a sequential set of bits set to 1 while all others are 0, and are used with an & to select particular bits out of a value.

Bit mask constants are generally written in hexadecimal; for example, 0x3ffe0 (or 0011 1111 1111 1110 0000₂) selects 13 bits, the 5th-least-significant through the 17th.

Bit mask computed values are generally built using shifts and negations; for example, ((~0)<<5) ^ ((~0)<<14) generates 0x3fe0:

Expression	binary	description	alternative constructions
`0`	…`00000000000000000`	all zeros
`~0`	…`11111111111111111`	all ones	`-1`
`(~0)<<5`	…`11111111111100000`	ones with 5 zeros in the bottom place	`~((1<<5)-1)`
`(~0)<<14`	…`11100000000000000`	ones with 14 zeros in the bottom place	`~((1<<14)-1)`
`((~0)<<5) ^ ((~0)<<14)`	…`00011111111100000`	9 ones, 5 places from bottom	`((1<<9)-1)<<5`, `(~((~0)<<9))<<5`

3 Bit terminology

When discussing a sequence of bits, some terms are used in multiple ways:

Bit Vector

A common name for a fixed-length sequence of bits, implemented using one of a programming language’s built-in integer types, manipulated primarily by bitwise operations.

Also a name for a more complicated data structure that stores any number of one-bit values.

Clear

As a verb, either replace a single bit with 0 or replace all bits with 0. To clear the 4th bit of x, you’d do x &= ~(1<<4). To clear x, you’d do x &= 0.

As a noun, is zero, usually of a specific bit. To check if the 4th bit of x is clear you’d do (x & (1<<4)) == 0.

ith bit

Usually the bit which, in a numeric interpretation, would be in the 2ⁱs place (i.e., the 3rd bit is in the 8s place): in other words, counting from least- to most-significant starting at 0. A number with just the kth bit a 1 can be created as 1<<k. Unless otherwise specified, this is the usage of bit ordinals throughout this text.

Sometimes starts counting from the most- instead of least-significant bit.

Sometimes counts from 1 instead of 0.

Sometimes people use th for all 0-based bit counting (e.g., the 1th bit instead of the 1st bit)

Set

Sometimes a verb, set this bit, meaning make it a 1. To set the 4th bit of x, you’d do x |= 1<<4.

Sometimes an adjective, meaning a bit position containing a 1. Thus in the number 1100110₂ the 2nd bit is set but the 3rd is not.

Zero

Sometimes the opposite of 1 as related to a single bit.

Sometimes a bit vector of all 0 bits.

Sometimes a synonym for clear. The verb form is also sometimes rendered zero out.

4 Flags and bitvectors as sets

One common practical use of bit manipulation in programming is the concise representation of sets of Boolean values. Given a small fixed set of possible elements of a set, any particular set of those elements can be efficiently represented by a number, where each possible element is assigned a unique bit within a number. For example, if our possible set of elements is {fun, important, required, useful, good prof, good time} we might say

FUN       = 1<<0
IMPORTANT = 1<<1
REQUIRED  = 1<<2
USEFUL    = 1<<3
GOOD_PROF = 1<<4
GOOD_TIME = 1<<5

and then GOOD_TIME | FUN | GOOD_PROF (i.e., 110001₂ or 0x31 or 49) would represent a filler elective, while 0xE (or 14 or IMPORTANT | REQUIRED | USEFUL) would represent a class you know will be good for you, even if you don’t enjoy it.

Each single-set-bit value is called a flag²² There is a related concept used in circuit design called one-hot encoding which also has values with just one non-0 bit, but that term is rarely used in software. and a set represented by the bitwise-or of zero or more flags is often just called the flags.

Given a set represented as flags-variable x, we can write set operations as follows:

Set operation	Bitwise
a ∈ x	`(A & x) != 0`
{a} ∪ x	`A \| x`
x ∖ {a}	`x & ~A`

Set datatype action	Bitwise
`x.contains(A)`	`(x & A) != 0`
`x.add(A)`	`x \|= A`
`x.remove(A)`	`x &= ~A`

5 Bit-fiddling

Bit-fiddling is a colloquialism for using sequences of operations to achieve various bit-level transformations of values. While rarely of intrinsic importance in programming, they show up often enough in practice that they sometimes make it into technical interviews and the like.

Suppose you want to retrieve k bits from x, starting at bit i. You’d first shift x to the right so the last i bits are not there:

x >>= i

and then mask out the last k bits

x &= (1<<k)-1

Suppose you wanted to compute the parity of a 32-bit vector x, as described in the section Parity, checksums, error-correction codes, and digests. You could brute-force it:

parity = 0
repeat 32 times:
    parity ^= (x&1)
    x >>= 1

That has a total of 32 xors, 32 ands, and 32 shifts. We can do it much more efficiently than that.

Observe that xor is both transitive and associative; thus we can re-write $x_0 ⊕ x_1 ⊕ x_2 ⊕ x_3 ⊕ x_4 ⊕ x_5 ⊕ x_6 ⊕ x_7$ using transitivity as $x_0 ⊕ x_4 ⊕ x_1 ⊕ x_5 ⊕ x_2 ⊕ x_6 ⊕ x_3 ⊕ x_7$ and using associativity as $(x_0 ⊕ x_4) ⊕ (x_1 ⊕ x_5) ⊕ (x_2 ⊕ x_6) ⊕ (x_3 ⊕ x_7)$ and then compute the contents of all the parentheses at once via x ^ (x>>4). Repeating this kind of computation at scale, we have

x ^= (x>>16)
x ^= (x>>8)
x ^= (x>>4)
x ^= (x>>2)
x ^= (x>>1)
parity = (x & 1)

That’s just 5 xors, 1 and, and 5 shifts.

A lot of bit-fiddling is about finding these kinds of shortcuts and tricks. Software engineers often find these shortcuts distasteful and confusing, but in some rare circumstances bit fiddling can provide significant memory or speed benefits.

Consider the following bit-fiddling code:

x ^= y
y ^= x
x ^= y

Try this out with various initial values of x and y and write a description of what this code is doing.
Work out by hand the contents of each variable in terms of the original values of x and y; for example, after running the first line x contains $x_0 ⊕ y_0$ . Using the identities $a ⊕ a = 0$ and $0 ⊕ x = x$ , prove that your description from part 1 is true.
Explain why a good software engineer should never use this code.