"Dibbles" and "Tribbles" ... love 'em!
Another issue is the arithmetic concersion issue. If two dibbles, represented as bytes, are to be multiplied, Java will convert the bytes to ints. Then after the multiplication, the result has to be cast back to byte. If arithmetic isn't carefully managed, all the conversion and casting could chew up a lot of time.
Thinking out loud here, I would be tempted to use lookup tables for arithmetic. Suppose I want to multiply a pair of dibbles, one in bits 1:0 of its byte and one in bits 3:2 of its (different) byte. Assuming all other bits are zero (that is, the other dibbles or tribbles have been masked out and I'm now dealing with ints), I would add the dibbles and use the result as an index into a byte array. I would have one array for addition results, one for subtraction, etc.
I'm really enjoying typing "dibble" and "tribble" so I'm going to do it once more before signing off. Dibble. Tribble.