Bitwise arithmetic
CS 301 Lecture, Dr. Lawlor, 2005/09/12
Last class, we looked at C's bitwise operators. I should
point out that you can use all these operators in perfectly ordinary
C/C++/Java/C# code:
int A=0x6789, B=0xF;
int C=A&~B; /* Now C==0x6780 */
This works fine everywhere. You can also work examples in Windows
using the Calculator accessory, or on a UNIX machine using the "bc"
command line tool (set input and output to binary using "obase=2;
ibase=2;" to hex using "obase=16; ibase=16;").
Arithmetic In Binary
We can do arithmetic in binary or hex by hand just like we do in
decimal. To add, line up the digits, add corresponding digits, and if
the per-digit sum is greater than the base, carry to the next digit. Easy,
right? To subtract, do the exact same thing, but "borrow" from
the next digit if the per-digit difference is less than 0.
For example, in binary 01+01=10 because the first digit overflows, and
the extra "1" is carried to the next digit. Similarly,
1111+1=10000 because all the digits overflow in sequence. In
general, adding a "1" will cause carries to ripple up through ones,
flipping them to zeros, until it finally reaches a zero, which it will
flip to a one.
Addition in hex is exactly the same--it's a bit tricker to add the
larger digits involved, but carries work exactly the same.
So 0x8+0x8=0x10, and 0xffff+0x1=0x10000.
Subtraction in binary seems really bizarre until you remember than
10-1=1 in binary--that is, "1" is the one-less-than-zero digit in
binary like "9" is the corresponding digit in decimal. So when
you have to borrow, you just flip the zeros to ones until you hit a
one.
Subtraction actually shows you how to represent negative numbers in
binary. Consider -1==0-1: you just keep on flipping zeros to ones
forever, "borrowing" against the future that never comes. So -1
is represented (in principle) by an infinite number of ones, just like
+1 is represented (in principle) by an infinite number of zeros
followed by a one. In practice, we only store a finite number
(usually 32 or 64) of bits, so on a 32-bit machine we define 32 ones as
-1. The highest bit, then, can be thought of as a "sign
bit"--negative numbers have that bit set, positive numbers have that
bit clear. Suprisingly, it make sense to think of the sign bit in
digit n as having value -2n, instead of value 2n for unsigned numbers. What's weirder is that addition and subtraction are exactly the same
for signed or unsigned numbers--try it! (All other operations are
different, though: comparison, multiplication, division, etc.)
This is clearer if you draw it out for a 3-bit machine:
Bit Pattern
|
Unsigned Value
|
Signed Value
|
000
|
0
|
0
|
001
|
1
|
1
|
010
|
2
|
2
|
011
|
3
|
3
|
100
|
4
|
-4
|
101
|
5
|
-3
|
110
|
6
|
-2
|
111
|
7
|
-1
|
Note that everything but Java supports "signed" as well as "unsigned"
integers explicitly. In C/C++/C#, typecasting to an unsigned
value does nothing to the bits, and is hence a zero-clock
operation. One way to speed up a "zero to n" bounds test on a
signed value is to turn it into an unsigned value and just compare
against n--that is, "if ((x>=0)&&(x<n)) ..." is the same
as "if (((unsigned int)x)<n) ..." do exactly the same thing, because
negative signed x's will turn into really huge unsigned x's!
Arithmetic Version of Bitwise Operations
Think about what "A<<1" does to the bits of an integer: what was
in the 1's place is now in the 2's place, 2's are shifted to 4's place,
4 is shifted to 8's place, etc. That is, all the bits are now in
places worth twice as much as before, so the overall integer is worth
twice as much as before: "(A<<1) == (A*2)". In general,
left-shifting by n bits is a fast way to multiply by 2n.
Correspondingly, "A>>1" pushes everything into lower-valued
places, and drops the lowest digit. This means it's equivalent to
division: "(A>>1) == (A/2)". In general, right-shifting by
n bits is a fast way to divide by 2n (and ignore the remainder).
You might think right shifting a negative number would bring in zeros,
hence flipping it into a positive number, but in C/C++/C# the
">>" operator actually does the correct thing--it brings in zeros
for unsigned values, and brings in the sign bit for signed
values. Java doesn't have an "unsigned" data type, but it does
have an arithmetic right-shift called ">>>" that brings in
zeros; ">>" assumes signed by default.
Finally, "A&0x1" drops all digits higher than the 1's place, so the
result is either 0 or 1 corresponding to whether A was even or odd;
that is, it's the modulo-2 operation (remainder after dividing by 2),
so "(A&0x1)==(A%2)". Similarly, "A&0x3" gives a result
from 0-3, corresponding to the version of A where we've dropped
corresponding the higher binary digits, so
"(A&0x3)==A%4". So masking is a fast way to do modulus
operation.
All three of these can be used to speed up arithmetic: multiplying is
pretty fast on modern machines, but it's not (quite) as fast as bit
shifting. Division and modulus operations are really quite slow
on most machines, so replacing them by bitshifts can often give a 20x
speedup! Keep in mind, though, that the compiler also knows about
these tricks--so if you write "A/4" somewhere, the compiler will almost
always use the bit shift instead of the divide. The only place
the compiler won't help you is when it doesn't know what you're
dividing by--so if you write "A/B", even if B always turns out to be a
power of two, the compiler will use the slow divide instruction instead
of a fast bit shift. This means you may have to keep track
of the corresponding bit shift (log-base-2 of B) or bit mask (for B a
power of two, it's just B-1) manually, which is a pain, but sometimes
speed hurts!
Once place where bit-style arithmetic operations really shine is with
packed fields. Let's say you've got two packed ARGB colors A and
B (i.e., four 8-bit fields) that you want to average--blend together at
50% intensity. The usual way to do this would be to extract the
alpha, red, green, and blue fields (using masking and bit shifts),
blend them by adding them together and dividing by two, and reassemble
them using more bit shifts and OR operations--a total of like
4*(2+2+2)=24 operations, including four divides. But it's way
faster to do this:
int blend=((A>>1)&0x7f7f7f7f)+((B>>1)&0x7f7f7f7f);
That is, we divide all
the fields of both inputs by 2 using a bit shift, mask off space for
the (overflow or carry) in the high bit, and add. This gives you
a four-color blend operation for the cost of 5 cheap single-clock bit
operations! Michael Herf has a great page on a similar trick for weighted blending.