Bitwise Operations

Introduction

Bitwise operators looked like noise to me for a long time. flags & READ_ONLY, x << 3, ~mask: I'd copy them from examples and hope. Then I spent an evening flipping bits by hand on paper and realized there are only six operators and each one does something very simple. This post is that evening, plus a demo so you don't need the paper.

Numbers are bits

An 8-bit integer is eight switches. Each switch is worth a power of two, from 128 on the left down to 1 on the right.

bit:    7    6    5    4    3    2    1    0
worth: 128   64   32   16    8    4    2    1

0b10110010 is 128 + 32 + 16 + 2 = 178. Bitwise operators work on those switches directly, one position at a time, instead of on the number as a whole.

The operators

• AND &: the result bit is 1 only if both input bits are 1.
• OR |: the result bit is 1 if either input bit is 1.
• XOR ^: the result bit is 1 if the input bits are different.
• NOT ~: flips every bit.
• Left shift <<: slides all bits left, filling with zeros. Each shift doubles the number.
• Right shift >>: slides all bits right. Each shift halves the number, dropping the remainder.

Try it

Pick an operator, then click bits in a and b to flip them and watch the result. Try XOR-ing a number with itself, or shifting 1 left a few times.

Where you'll actually use them

Flags

The most common use. Pack several yes/no options into one integer, one bit each.

#define READ    (1 << 0)   // 0001
#define WRITE   (1 << 1)   // 0010
#define EXECUTE (1 << 2)   // 0100

int perms = READ | WRITE;        // set: 0011

if (perms & WRITE) { /* on */ }  // test: nonzero if the bit is set

perms |= EXECUTE;                // turn on:  0111
perms &= ~WRITE;                 // turn off: 0101
perms ^= READ;                   // toggle:   0100

Four idioms worth memorizing: | to set, & to test, & ~ to clear, ^ to toggle. This is exactly how Unix file permissions and most C APIs with an int flags argument work.

Fast multiply and divide by powers of two

x << 3 is x * 8 and x >> 1 is x / 2. Compilers do this for you now, but you'll see it in older code and in anything that cares about every cycle.

Masking

AND with a mask to keep only the bits you want. Pulling the low byte out of a 32-bit integer:

unsigned int color = 0x00FF8040;
unsigned char blue  = color & 0xFF;          // 0x40
unsigned char green = (color >> 8) & 0xFF;   // 0x80
unsigned char red   = (color >> 16) & 0xFF;  // 0xFF

Checking even or odd

n & 1 is 1 for odd numbers and 0 for even ones. The lowest bit is the ones place.

Swapping without a temp variable

A party trick more than a tool, but it shows how XOR works: XOR-ing with the same value twice gets you back where you started.

a ^= b;
b ^= a;
a ^= b;

Two things that bit me

Shifting signed numbers. Right-shifting a negative int is implementation-defined in C. Some compilers fill with the sign bit, some with zero. Use unsigned types for bit manipulation and this goes away.

Operator precedence. & and | bind weaker than ==, so if (flags & WRITE == WRITE) parses as flags & (WRITE == WRITE), which is flags & 1. Always parenthesize: if ((flags & WRITE) == WRITE), or just if (flags & WRITE).

Conclusion

Six operators, each one doing something simple to each bit position. The flag idioms (| set, & test, & ~ clear, ^ toggle) cover most real-world uses, and the demo above is faster than paper for everything else.