Intro. to Bitwise Operators

This article will deal with an introduction to bitwise operators, written in the way that most makes sense to me, from a hardware and low-level software point of view. The basics apply to anyone, though those working in higher-level languages may only care about how to use them and nothing more in depth.

There are a lot of bitwise operators. They are important in programming and represent essentially all combinational digital logic. Bitwise operators operate on the individual bits of a variable. For example, where you see the number 20 (stored as an unsigned byte), a bitwise operator sees 0x14 or 0b00010100. It doesn't care about the integer 20; it cares about the sequence of bits.

AND operator: 1 if both bits are 1, 0 otherwise A | B | A AND B 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 AND usage: Let A = 5 A = 0b101

Let B = 3 B = 0b011

A AND B 101 AND 011 --- RESULT 001 A & B == 0b001 == 1 base 10

Hopefully this made sense - each bit column is ANDed irrespective of other columns. Now, let's list the most common operators:

A AND B: 1 if both bits 1 A OR B: 1 if at least one bit 1 A XOR B: 1 if exactly one bit 1 NOT A: 1 if bit is 0

Common notation in most programming languages (from low- to high-level ones):

A AND B: A & B A OR B: A | B A XOR B: A ^ B (note: xor means exclusive OR) NOT A: ~A

This should not be confused with boolean operators. They are very similar, but deal with the entire variable as a whole, instead of each bit. Common notations in most languages:

A AND B: A && B A OR B: A || B NOT A: !A

The difference is that a bitwise operator will return a value of the same type - for example, the bitwise OR of two ints will be an int - whereas a boolean operator returns a boolean value. Observe:

0b011 & 0b110 = 0b010 (bitwise AND of 3 and 6 is 2) 0b011 | 0b110 = 0b111 (bitwise OR of 3 and 6 is 7) 0b011 ^ 0b110 = 0b101 (bitwise XOR of 3 and 6 is 5) ~ 0b011 = 0b100 (bitwise NOT of 3 is 4) Compared to 0b011 && 0b110 = TRUE (both values non-zero) 0b011 || 0b110 = TRUE (at least one value is non-zero) ! 0b011 = FALSE (NOT of non-zero is zero, is FALSE)

As you can see, AND, OR, XOR take two operators, but NOT takes just one. AND, OR, XOR can be extended to take more than two operators. Depending on the implementation, this is either decomposed into multiple operations, or executed as one operation. The choice of decomposition or executing at once is made on various levels - for example, decomposition can happen at interpretation, compilation, decode from macro-operation to micro-operation, inside the actual ALU, or even on the gate or transistor level. Consider the following case:

AND: result 1 if all inputs 1 A | B | C | A & B & C 0 | 0 | 0 | 0 0 | 0 | 1 | 0 0 | 1 | 0 | 0 0 | 1 | 1 | 0 1 | 0 | 0 | 0 1 | 0 | 1 | 0 1 | 1 | 0 | 0 1 | 1 | 1 | 1 Decomposition: A & B & C == (A & B) & C, or A & (B & C), which are equivalent -------------------------------------------------------------- Interpeted language: dest = A & B & C Decomposition: code executed by interpreter temp1 = A & B dest = temp1 & C -------------------------------------------------------------- Compiled language: dest = A & B & C Decomposition: assembly - or equivalent hex ; assume values loaded into r8, r9, r10 ; assume dest will be r8 and r8, r9 ; r8 = r8 & r9 = (A) & (B) and r8, r10 ; r8 = r8 & r10 = (A & B) & C -------------------------------------------------------------- Assembly language: and r8, r9, r10 ; r8 = r8 & r9 & r10 Decomposition: micro-operations, or uops uop_and r8, r9 ; r8 = r8 & r9 uop_and r8, r10 ; r8 = r8 & r10 -------------------------------------------------------------- Micro-operation: uop_and r8, r9, r10 Decomposition: physical hardware -------------------------------------------------------------- Gate level: Decomposition: transistor level hardware

Decompositions in notation common to most programming languages:

A & B & C (A & B) & C == A & (B & C) 1 if all bits 1 A | B | C (A | B) | C == A | (B | C) 1 if at least one bit 1 A ^ B ^ C (A ^ B) ^ C == A ^ (B ^ C) 1 if odd number of bits 1

Those are the most-used bitwise operators. Here are some that complement the ones we've seen:

NAND inverse of AND 1 if NOT (all bits 1) 1 if at least 1 bit 0 NOR inverse or OF 1 if NOT (at least 1 bit 1) 1 if all bits 0 XNOR inverse of XOR 1 if NOT (odd number of bits 1) 1 if even number of bits 1

And the last bitwise operators deal with shifting (arithmetic versus logical bit shift not covered here):

Let A = 0b0011 SHL: Shift Left (all bits shifted left) A << 1 A << 2 A == 0b0110 A == 0b1100 SHR: Shift Right (all bits shifted right) A >> 1 A >> 2 A == 0b0001 A == 0b0000

This leads us into the next topic: Dangers of bitwise shifting!

Ches Koblents

September 9, 2013

September 9, 2013