Bitwise Operations

CS 301 Lecture, Dr. Lawlor

Bitwise Operations in C

There are actually six bitwise operators in C/C++/Java:
Here's the "truth table" for the 3 main binary bitwise operations: AND, OR, and XOR.  Again, these are accessible directly from all C-like languages using '&' (ampersand or just "and"), '|' (pipe or just "or"), and '^' (caret or just "ex-oar").
A
 B
 A&B (AND)
 A|B (OR)
 A^B (XOR)
0
 0
 0
 0
 0
0
 1
 0
 1
 1
1
 0
 0
 1
 1
1
 1
 1
 1
 0
Interpretations:
Both-1 Either-1 Different


Spreads-0
 Spreads-1
 Flip A if B is set

Say you're Google.  For each possible word, you store a big list of documents containing one 32-bit integer per document.  Each bit of that integer corresponds to a section of the document where the word might occur (e.g., bit 0 is set if the word occurs in the first 3% of the document, bit 1 represents the next 3%, and so on).  If you've got two search terms, for a given document you can look up two integers, A and B, that represent where those terms appear in the document.  If both terms appear near the same place in the document, that's good--and we can find a list of all those places (where both bits are set to 1) in just one clock cycle using just "A&B"!  The same idea shows up in the "region codes" of Cohen-Sutherland clipping, used in computer graphics.

But what if I want to compare two documents for similarity?  Note that C-like languages don't provide a "bitwise-compare" operator, that sets equal bits to 1 and unequal bits to 0 (because == compares whole integers, not individual bits).  So how can you compute this?

Well, all the bitwise operations do interesting and useful things when inverted:
A
 B
 ~(A&B) (NAND)
 ~(A|B) (NOR)
 ~(A^B) (XNOR)
0
 0
 1
 1
 1
0
 1
 1
 0
 0
1
 0
 1
 0
 0
1
 1
 0
 0
 1
Interpretations:
Either-0
 Both-0 Equality

Note that "~(A^B)" is 1 if both input bits are identical, and 0 if they're different--so it's perfect for computing document similarity!

The final major bitwise operation is bit shifting, represented in C-like languages using ">>" and "<<".  Left shift ("<<", pointing left), shifts bits into higher positions, filling the now-empty lower positions with zeros.  For unsigned numbers, right shifting (">>", pointing right) shifts bits into lower positions and fills the empties with zeros.  If you wants to search for both-term matches in B that are one bit off of those in A, you can use "A&(B<<1)" or "A&(B>>1)", depending on the direction you want to check.  To check both directions, use "(A&(B<<1))|(A&(B>>1))".

One warning: bitwise operations have strange precedence.  Specifically, "A&B==C" is interpreted by default like "A&(B==C)", not "(A&B)==C"; and "A>>B+C" is interpreted as "A>>(B+C)".  This can cause horrible, hard-to-understand errors, so I just stick in parenthesis around everything when I'm using bitwise operators.

Bitwise Algebra

If A and B are random integers, "A&B", "A|B", and "A^B" don't have any obvious numerical relationship to A and B.  But there are lots of useful relationships for special cases:

Applications of Bitwise Operations--Thinking in SIMD

The simplest bitwise operation is the NOT operation: NOT 0 is 1; NOT 1 is 0.  Bitwise NOT is written as "~" in C/C++/Java/C#.   The cool thing about the NOT (and other bitwise) operations is that they operate on *all* the bits of an integer at *once*.  That means a 32-bit integer NOT does thirty-two separate things at the same time!  This "single-instruction, multiple data" (SIMD) approach is a really common way to speed up computations; it's the basis of the MMX, SSE, and AltiVec instruction set extensions. But you can do lots interesting SIMD work without using any special instructions--plain old C will do.  This use of bitwise operations is often called "SIMD within a register (SWAR)" or "word-SIMD"; see Sean Anderson's "Bit Twiddling Hacks" for a variety of amazing examples.

The genome uses just 4 digits (ACGT, for the acids Adenine, Cytosine, Guanine, and Thymine), and so can be represented in as few as 2 bits per nucleotide (genetic digit).  Former UAF CS undergraduate James Long, now up the hill at ARSC, developed a very fast sofware implementation of the Smith-Waterman string (or gene) matching algorithm called CBL that uses this SIMD-within-a-register approach.

What's the deal with hex?

Humans have used the "place/value" number system for a long time--the Sumerians used base-60 in 4000BC! (Base-60 still shows up in our measurement of time (hours have 60 minutes, which have 60 seconds) and angles (360 degrees)).  The Maya used base 20.  The world standard, though, is now base 10 using Arabic numerals.  For example, I'm 29 = 2 * 10 + 9 years old.

Place Number:
 i
 ...
 3
 2
 1
 0
Base-10 value
 10i
1000
 100
 10
 1
Base-2 value
 2i
8
 4
 2
 1
Base-1
value
 1i
1
 1
 1
 1
Base-16 value
 16i
4096=163 256=162
 16
 1
Base-n
 ni
n3 n2 n
 1

But every computer built today uses binary--1's and 0's--to do its work.  The reason is electrical--0 is no current, 1 is current.  Having just two states makes it easy to build reliable circuits; for example, a transistor will threshold the input value and either conduct or not conduct.  A single zero or one is called a "bit". 

OK, so we got 1's and 0's: how to we build bigger numbers?  There are two ways: the older method, called "binary coded decimal" (BCD), was to first build decimal digits using binary, then interpret the decimal numbers in the usual way--the complication being that arithmetic is tricky in decimal, as any grade schooler can attest!  Older machines, like the Motorola 68K, had hardware support for BCD computations.   But the modern standard method is using "binary", which is just the place-value system using base 2.  In binary, 1 means 1; 10 (base 2) means 2 (base 10); 100 (base 2) means 4 (base 10); 1000 (base 4) means 8 (base 10);  10000 (base 2) means 16 (base 10); and so on.  Every machine produced today supports direct binary arithmetic.

Eight bits make a "byte" (note: it's pronounced exactly like "bite", but always spelled with a 'y'), although in some rare networking manuals (and in French) the same eight bits would be called an "octet".  There are theoretically some other measurements like a four-bit "nybble", but these are quite rare, and basically just jokes.   In DOS and Windows programming, 16 bits is a "word", and 32 bits is a "dword" (double word); but in other contexts "word" means the machine's natural binary processing size, which ranges from 8 to 64 bits nowadays.

Sadly, (for a human!) writing or reading binary is really painful and error-prone for large numbers.  For example, one million is 11110100001001000000 (base 2), which is painful to write or read.  So instead, we often use a larger base.  Back in the 1970's, it was pretty common to use octal (base 8), but the modern standard is hexadecimal--base 16.  Base 16's gotta use 16 different digits, and there are only 10 arabic numerals, so we use normal alphabet letters for the remaining digits.  For example, 15 (base 10) is just F (base 16); an one million in hex is F4240 (base 16).  You've got to be careful about the base, though--the string "11" would be interpreted as having the value 1*2+1=3 if it was base 2, the usual 1*10+1=11 if it was base 10, or 1*16+1=17 in base 16!

Note that a single digit in base 16 corresponds to exactly 4 bits, since 16=2*2*2*2.  This means it's easy to convert from a binary number to a hex number: take groups of 4 bits and convert to a hex digit--or back again: take each hex digit and expand out to 4 bits. 

Hex really is the only true universal in assembly and disassembly.  For example, here's some random disassembled code (produced using "objdump --disassemble /bin/ls" on a Linux machine):
 80561a6:       83 ec 0c                sub    $0xc,%esp
 80561a9:       e8 ea ff ff ff          call   80561f8 <__i686.get_pc_thunk.bx>
Note that every single number is listed in hex--the addresses, on the left; the machine code, in the middle; and the constants in the assembly, on the right.  A binary file display tool is called a "hex dump".  A binary file editor is called a "hex editor".  That's how common hex is, so for the rest of the class to make sense, you've gotta learn it!

Bit-field Interpretation of Bitwise Operations

So we've seen what interesting things can be done with bitwise operations on a pile of bits.  Another major use of bitwise operations is for "bit fields", where you've divided up the parts of an integer into smaller pieces. 

The smallet possible bit field has only one bit in it.  So you might check if the low bit of x is set by testing
    if ((x&1) == 1) ...
You can check the next-higher bit by testing
    if ((x&2) == 2) ...
To check bit n, test
   if ((x&(1<<n))==(1<<n)) ...
or equivalently
   if (((x>>n)&1)==1) ...

If you've got 2 possible values, you only need one bit.  To chop something down to n bits, you can "mask" it by ANDing with a value where the bits less than n are set to 1, and bits n and higher are cleared to 0.  For example, 0xFF has bits 8 and higher clear, so you can chop a value down to 8 bits by ANDing by 0xff.  Note that this removes all powers of two at 2n and beyond, so after masking the value will run from 0 to 2n-1.  Beware: normal machines only keep a small number of bits, like 32 or 64, in each integer, and the *hardware* masks off arithmetic results (by throwing away bits) to fit in this space!  This is called "wraparound" or "overflow", and it can cause lots of surprising errors.

Number of Values
 Number of bits
 Mask (hex)
2
 1
 0x1
4
 2
 0x3
8
 3
 0x7
16
 4
 0xF
32
 5
 0x1F
64
 6
 0x3F
128
 7
 0x7F
256
 8
 0xFF
65,536
 16
 0xFFFF
4,294,967,296
 32
 0xFFFFFFFF
2n n
 2n-1


For example, let's say you're trying to decode data written by a satellite radar sensor, which uses 4 bits each for its "I" and "Q" values (which have 16 possible values each), and stores them together in one integer "A" like this:
Name
 I
 Q
Size
 4 bits
 4 bits
Starting bit in A
 Bit 4
 Bit 0
So "I" is stored in the high 4 bits of A, and "Q" is in the low 4 bits of A.  For example, if A==0xA7, the I field would be 0xA and the Q field would be 0x7.

To extract out just the Q field, we've just got to get rid of the bits that store I somehow.  The standard way to do this is to use the AND operation to set all the bits of I to zero--zero AND anything is zero, so "Q=A&0x0F".  That is, we've used 0xF to mask off the bits above Q.

To extract out the I field, we've got to get rid of Q (as before), but we've also got to shift I down so it starts at bit zero.  We can do this using "I=(A&0xF0)>>4".  Or, because right-shift throws away bits that fall off the right end, we can also just use "I=A>>4".

To stick A back together from separate I and Q values, we just shift I and Q into the right places, then OR them together, like "A=(I<<4)|Q".   Or if you really want to be persnickety, "A=(I<<4)|(Q<<0)", which is redundant because the ">>0" doesn't do anything. If you're really paranoid, you'll mask off any high bits, like "A=(0xF0&(I<<4))|(0x0F&(Q<<0))", but this isn't needed if I and Q don't have any high bits set.


This "keep a bunch of bitfields in one integer" technique is in found all over the place in machine code.  In x86 machine code, the "SIB" byte stores a scale, index, and base (that we'll learn the details of later) as:
Name
 Scale
 Index
Base
Size
 2 bits
 3 bits
3 bits
Starting bit
 Bit 6
 Bit 3
Bit 0

We can reassemble a SIB byte like "SIB=(Scale<<6)|(Index<<3)|Base"; and extract out the fields like "Scale=0x3&(SIB>>6)", "Index=0x7&(SIB>>3)", and "Base=0x7&SIB".


Bit shifts and masks are found everywhere in code that talks to hardware.  For example, here's a snippet from the Linux 2.6.5 kernel, linux/drivers/usb/storage/sddr09.c line 1239.
                if ((ptr[6] >> 4) != 0x01) {
                        printk("sddr09: PBA %d has invalid address field "
So this is verifying that the high 4 bits of "ptr" (a char pointer) actually equal 0001.  There are a zillion equivalent ways to write this same thing, though: