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!

0xf0d<<4 == 0xf0d0

0xf0d>>4 == 0xf0

Bitwise operators make perfect sense working with hex digits, because they operate on the underlying bits of those digits:

0xff0 & 0x0ff == 0x0f0

0xff0 | 0x0ff == 0xfff

0xff0 ^ 0x0ff == 0xf0f

You can use these bitwise operators to peel off the hex digits of a number, to print out stuff in hex:

int v=1024+15;

for (int digit=7;digit>=0;digit--) {

char *digitTable="0123456789abcdef";

int d=(v>>(digit*4))&0xF;

std::cout<<digitTable[d];

}

std::cout<<std::endl;

return v;

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 1 followed by n zeros.
- The value of (k<<n) is actually k*2
^{n}. This means bit shifting can be used as a faster multiply by a power of two. - 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.

In assembly:

- shl is "shift left". Use it like "shl eax,4" (Try this in NetRun now!). Note that the '4' can be a constant, or register cl (low bits of ecx), but not any other register (Try this in NetRun now!).
- sal is the same instruction (same machine code).
- There's also a "rol" that does a circular left shift: the bits leaving the left side come back in the right side.

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.

- On a 32-bit machine, (k>>32) == 0, plus a compiler warning, because all the bits of k have fallen off the end.
- There are two flavors of right shift: signed, and unsigned.
Unsigned shift fills in the new bits with zeros. Signed shift
fills the new bits with copies of the sign bit, so negative numbers
stay negative after the shift.

- 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)

- shr is the unsigned shift.
- sar is the signed (or "arithmetic") shift.

- Again, there's a circular right shift "ror".

As Ints |
As Bits |

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

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

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

Properties:

- 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!

In assembly, it's the "and" instruction. Very simple!

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.

(2&&4) == 1 (because both 2 and 4 are nonzero)

(2&4) == 0 (because 2==0010 and 4 == 0100 don't have any overlapping one bits).

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];

}