Bitwise Operations

CS 301: Assembly Language Programming Lecture, Dr. Lawlor

There are a whole group of "bitwise" operators that operate on bits.
Name
C++
x86
Useful to...
AND
&
and
mask out bits (set other bits to zero)
OR
|
or
reassemble bit fields
XOR
^
xor
invert selected bits
NOT
~
not
invert all the bits in a number
Left shift
<<
shl
makes numbers bigger by shifting their bits to higher places
Right shift
>>
shr
sar
SHift Right: makes numbers smaller by shifting their bits to lower places.
Shift Arithmetic Right: signed shift retains sign bit for negative numbers.

If you'd like to see the bits inside a number, you can loop over the bits and use AND to extract each bit:

int i=9; // 9 == 8 + 1 == 1001

for (long bit=31;bit>=0;bit--) { // print each bit
	long mask=(1L<<bit); // only this bit is set
	long biti=mask&i; // extract this bit from i
	if (biti!=0) std::cout<<"1";
	else         std::cout<<"0";
}
std::cout<<" integer\n";

(Try this in NetRun now!)

Because binary is hard to read (was that 1000000000000000 or 10000000000000000?), we normally use hexadecimal, base 16.

Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Hex 0 1 2 3 4 5 6 7 8 9 A B C D E F 10
Binary 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

Remember that every hex digit represents four bits.  So if you shift a hex constant by four bits, it shifts by one entire hex digit:

    0xf0d<<4 == 0xf0d0
    0xf0d>>4 == 0xf0

If you shift a hex constant by a non-multiple of four bits, you end up interleaving the hex digits of the constant, which is confusing:

   0xf0>>2 == 0x3C (?)


Bitwise operators make more 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;

(Try this in NetRun now!)

You could also use printf("%X",v);

Bitwise Left Shift: <<

Makes values bigger, by shifting the value's bits into higher places, tacking on zeros in the vacated lower places. 

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:

In C++, the << operator is also overloaded for iostream output.  This was a confusing choice, in particular because "cout<<3<<0;" just prints 3, then 0!  To actually print the value of "3<<0", you need parenthesis, like this: "cout<<(3<<0);".  Operator precedence is screwy for bitwise operators, so you really want to use excess parenthesis!

In assembly:

Bitwise Right Shift: >>

Makes values smaller, by shifting them into lower-valued places.  Note the bits in the lowest places just "fall off the end" and vanish.

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:

If you're dyslexic, like me, the left shift << and right shift >> can be really tricky to tell apart.  I always remember it like this:

In assembly:

Bitwise AND: &

Output bits are 1 only if both corresponding input bits are 1.  This is useful to "mask out" bits you don't want, by ANDing them with zero.

As Ints As Bits
3&5 == 1 0011&0101 == 0001
3&6 == 2 0011&0110 == 0010
3&4 == 0 0011&0100 == 0000


Properties:

Bitwise AND is a really really useful tool for extracting bits from a number--you often create a "mask" value with 1's marking the bits you want, and AND by the mask.  For example, this code figures out if bit 2 of an integer is set:
    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!

Bitwise OR: |

Output bits are 1 if either input bit is 1.  E.g., 3|5 == 7; or 011 | 101 == 111.

As Ints As Bits
3|0 == 3 0011|0000 == 0011
3|3 == 3 0011|0011 == 0011
1|4 == 5 0001|0100 == 0101

 

Bitwise OR is useful for sticking together bit fields you've prepared separately.  Overall, you use AND to pick apart an integer's values, XOR and NOT to manipulate them, and finally OR to assemble them back together.

Bitwise XOR: ^

Output bits are 1 if either input bit is 1, but not both. E.g., 3^5 == 6; or 011 ^ 101 == 110.  Note how the low bit is 0, because both input bits are 1.

As Ints As Bits
3^5 == 6 0011&0101 == 0110
3^6 == 5 0011&0110 == 0101
3^4 == 7 0011&0100 == 0111

 

The second property, that XOR by 1 inverts the value, is useful for flipping a set of bits.  Generally, XOR is used for equality testing (a^b!=0 means a!=b), controlled bitwise inversion, and crypto.

There's a surprising way to swap two values without using temporary space using only three xor operations.

Bitwise NOT: ~

Output bits are 1 if the corresponding input bit is zero.  E.g., ~011 == 111....111100.  (The number of leading ones depends on the size of the machine's "int".)

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.

Non-bitwise Logical Operators

Note that the logical operators &&, ||, and ! work exactly the same as the bitwise values, but for exactly one bit.  Internally, these operators map multi-bit values to a single bit by treating zero as a zero bit, and nonzero values as a one bit.  So 
    (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).