So most of the usual work you do in C/C++/Java/C# manipulates integers or strings. For example, you'll write a simple line like:

x = y + 4;

which adds 4 to the value of y.

But sometimes you have to understand how this works internally. For example, on a 32-bit machine, this code returns... 0.

long x=1024;Why? The real answer is 4 billion (and change), which requires 33 bits: a 1 followed by 32 zero bits. But on a 32-bit machine, all you get is the zeros; the higher bits "overflow" and (at least in C/C++) are lost! Understanding the bits underneath your familiar integers can help you understand errors like this one. (Plus, by writing assembly code, you can actually recover the high-order bits after a multiplication if you need them.)

long y=x*x*x*4;

return y;

So because bits are important, C/C++/Java/C# include "bitwise" operators that manipulate the underlying bits of the integer. It's like the computer counts on its (32 or 64) fingers, does the operation on those bits, and then converts back to an integer. Except, of course, deep down the hardware only knows about bits, not integers!

As Ints |
As Bits |

3<<0 == 3 |
0011<<0 == 0011 |

3<<1 == 6 |
0011<<1 == 0110 |

3<<2 == 12 |
0011<<2 == 1100 |

Interesting facts about left shift:

- 1<<n pushes a 1 up into bit number n, creating the bit pattern 100... n zeros here ...00.
- The value of (k<<n) is actually k*2
^{n}. This means bit shifting can be used as a faster multiply. - k<<0 == k, for any k.
- (k<<n) >= k, for any n and k (unless you have "overflow"!).
- On a 32-bit machine, (k<<32) == 0, plus a compiler warning, because all the bits of k have overflowed away.

- Left shift always shifts in fresh new zero bits.

- You can left shift by as many bits as you want.
- You can't left shift by a negative number of bits.

As Ints |
As Bits |

3>>0 == 3 |
0011>>0 == 0011 |

3>>1 == 1 |
0011>>1 == 0001 |

3>>2 == 0 |
0011>>2 == 0000 |

6>>1 == 3 |
0110>>1 == 0011 |

Interesting facts about right shift:

- The value of (k>>n) is actually k/2
^{n}. This can be used as a faster divide. - (k<<n)>>n == k, unless overflow has happened.

- Right shift can do strange things to negative values (we'll talk about negative values later).
- On a 32-bit machine, (k>>32) == 0, plus a compiler warning, because all the bits of k have fallen off the end.

- k<<n pumps up the value of k (the point of the << is injecting bigness into k)
- k>>n drains away the value of k (the point of the >> is draining bigness from k)

As Ints |
As Bits |

3&5 == 1 |
0011&0101 == 0001 |

3&6 == 2 |
0011&0110 == 0010 |

3&4 == 0 |
0011&0100 == 0000 |

- 0=A&0 (AND by 0's creates 0's--used for masking)
- A=A&~0 (AND by 1's has no effect)
- A=A&A (AND by yourself has no effect)

int mask=(1<<2); // in binary: 100

int value=...; // in binary: xyz

if (0!=(mask&value)) // in binary: x00

...

In C/C++, bitwise AND has the wrong precedence--leaving out the parenthesis in the comparison above gives the wrong answer! Be sure to use extra parenthesis!

As Ints |
As Bits |

3|0 == 3 |
0011|0000 == 0011 |

3|3 == 3 |
0011|0011 == 0011 |

1|4 == 5 |
0001|0100 == 0101 |

- A=A|0 (OR by 0's has no effect)
- ~0=A|~0 (OR by 1's creates 1's)
- A=A|A (OR by yourself has no effect)

As Ints |
As Bits |

3^5 == 6 |
0011&0101 == 0110 |

3^6 == 5 |
0011&0110 == 0101 |

3^4 == 7 |
0011&0100 == 0111 |

- A=A^0 (XOR by zeros has no effect)
- ~A = A ^ ~0 (XOR by 1's inverts all the bits)

- 0=A^A (XOR by yourself creates 0's--used in cryptography)

As Ints |
As Bits |

~0 == big value |
~...0000 == ...1111 |

I don't use bitwise NOT very often, but it's handy for making an integer whose bits are all 1: ~0 is all-ones.

enum {n=1}; // Number of integers in our tables (== size of internet / 32)The same bitwise testing idea shows up in the "region codes" of Cohen-Sutherland clipping, used in computer graphics.

unsigned int funky_table[n]={(1<<24)|(1<<17)|(1<<12)|(1<<4)};

unsigned int aardvark_table[n]={(1<<31)|(1<<24)|(1<<15)|(1<<6)|(1<<4)};

/* Match up the bits of these two tables using bitwise operations */

void both_tables(const unsigned int *a,const unsigned int *b,unsigned int *o) {

for (int i=0;i<n;i++) o[i]=a[i]&b[i]; /* bitwise AND */

}

/* Match up the bits of these two tables using logical (one-bit) operations */

void both_tables_logical(const unsigned int *a,const unsigned int *b,unsigned int *o)

{

for (int i=0;i<n;i++) {

o[i]=0;

for (int bit=0;bit<32;bit++)

{

unsigned int a_bit=a[i]&(1<<bit);

unsigned int b_bit=b[i]&(1<<bit);

if (a_bit && b_bit) /* logical AND */

o[i]=o[i]|(1<<bit);

}

}

}

int foo(void) {

unsigned int output_table[n];

both_tables(funky_table,aardvark_table,output_table);

return output_table[0];

}