Bitwise operations in C¶
We’ve seen the ‘logical’ Boolean operators in C, i.e. &&
(AND), || (OR), and ! (NOT). They convert their operands
to Booleans, by the usual rule that anything equal to zero is false, and
anything else is true. So, although it looks a little weird, 13 &&
40 == true. This is very often what a programmer wants, but in another
way it is odd to treat, say, a 32-bit int as a 1-bit Boolean. What
if we wanted to use all 32 Booleans that integer is represented with?
C provides another set of Boolean operators, the ‘bitwise’ operators. Rather than converting multiple-bit operands to single bits, the bitwise operators instead stack them like in long addition and perform the usual Boolean operation on each column independently.
1 0 1 0 1 0 1 0
AND 0 1 1 0 1 1 0 0
───────────────────
0 0 1 0 1 0 0 0
1 0 1 0 1 0 1 0
OR 0 1 1 0 1 1 0 0
───────────────────
1 1 1 0 1 1 1 0
NOT 0 1 1 0 1 1 0 0
───────────────────
1 0 0 1 0 0 1 1
operator |
logical |
bitwise |
|---|---|---|
AND |
|
|
OR |
|
|
NOT |
|
|
XOR |
|
Although there is no logical XOR operator (other than doing your own
conversion to bool and using !=), there is a bitwise XOR
operator, ^. (There exist languages and conventions where the
caret character, ‘^’, is used for exponentiation; don’t get confused!
In C, x ^ y means XOR, not \(x^y\).) The bitwise versions
of AND and OR use the same character as the logical operators, but
singly instead of doubled. Bitwise NOT is a tilde, ~, which
you can think of as a little wave showing how all the bits flip over,
whereas logical NOT is an exclamation mark, !, similar to the
negative in !=.
Although not technically Boolean operators at all, there are a couple of arithmetic operators in C that are invaluable when working with larger values at the bitwise level: the shift operators. In general, multiplication is a non-trivial algorithm involving lots of subproducts and sums; however, you’re probably familiar with the trick in base 10 of multiplying by powers of 10 by simply ‘shifting’ the digits into different positions, as in \(843\times 10=8430\) or \(900\div 10=90\). In base 2, the same ‘shift’ trick works for multiplying or dividing by powers of 2.
C provides left (<<) and right (>>) shift operators for
multiplying and dividing, respectively, by powers of 2. The expression
x << y means \(x\cdot 2^y\) and x >> y means
\(\frac{x}{2^y}\), but specifically implemented by sliding the bits left
and right and padding them appropriately. Given how easy shifting is
in hardware, and how difficult multiplication is, a naïve implementation
of x * 4 could be many times slower than x << 2.
Any decent compiler will recognize and automatically convert multiplication to shifting when appropriate, so there is no need to worry about using one or the other for the sake of the speed of your programs. So, why have both? Use multiplication and division when that’s what you mean, and use shifting when you want to be explicit that your intent is to slide bits around.
The shift operators are defined for integer operands; they don’t apply to floating point or other types, and wouldn’t help there anyway because bit shifting isn’t equivalent to multiplication in floating-point representation. Left shift, i.e. multiplication by powers of two, simply slides each bit up and fills the space on the right with zeroes; of course, any bits at the top will be ‘shifted out’ and lost, which is a form of overflow. Right shift, i.e. division by powers of two, slides each bit down, and any bits on the right are ‘shifted out’, corresponding to truncating any fraction. The padding that slides in from the left depends on what kind of number is being shifted, in the same manner as sign extension: an unsigned integer always shifts in zeroes, while a two’s-complement integer shifts in copies of the sign bit.