Modular Arithmetic and Bit Manipulation #
Make sure you’re comfortable working with binary numbers (adding, subtracting, converting to decimal) before continuing.
Integer Types #
This is an excerpt from the chart in Java Objects. Go there to review primitive types first!
|short||16||yes||None - must cast from int|
|int||32||yes||123, 0100 (octal), 0xff (hex)|
|long||64||yes||123L, 0100L, 0xffL|
Signed Numbers #
A type is signed if it can be positive or negative. Unsigned types can only be positive.
In signed types, the first bit is reserved for determining the sign of the number (0 is positive, 1 is negative). This means that there is one fewer bit for the actual number. For example, ints only have 31 bits for the number.
Reading negative numbers #
Let’s say you are given a number like
10100and want to convert it to decimal. We know that the 1 in the front means it’s a negative number! However, we can’t just discard that 1 and read the rest like a positive number. Instead, we have to flip all the bits and then add one to the result. So,
10100 flipped will become
01011. Adding one will result in
01100, which is the correct answer (12).
Why do we have to do this? Read on to the next section to find out!
Two’s Complement #
Two’s Complement is a a method of storing negative numbers in a way that supports proper arithmetic. Here’s how it works:
- Start with a binary number we want to negate, like
0101, which is 5.
- Flip all the bits to make
- Add one to make
Although it makes negative numbers harder to read, the benefits are much more significant- it allows addition and subtraction to work between positive and negative numbers.
Modular Arithmetic #
Since primitive types have a fixed number of bits, it is possible to overflow them if we add numbers that are too large. For example, if we add
01000000(a byte) with itself, we’d need 9 bits to store the result!
This will cause lots of issues, so we use modular arithmetic to wrap around to the largest negative version and keep the number in bounds. For example,
(byte)128 (byte)(127+1) (byte)(-128).
Bit Operations #
A & Bwill only keep the bits that are 1 in A AND B
00101100 & 10100111 == 00100100
A | Bwill keep the bits that are 1 in A OR B
00101100 | 10100111 == 10101111
A ^ Bwill keep the bits that are 1 in A XOR B
- In other words, 1 if bits are unequal in A and B, 0 otherwise
00101100 ^ 10100111 == 10001011
Flip all: ~
~Awill flip all the bits from 1 to 0 or 0 to 1 in A
~10100111 == 01011000
Shift Left: «
A << nwill shift all bits left n places
- All newly introduced bits are 0
10101101 << 3 == 01001000
x << nis equal to x * 2^n
Arithmetic Right: »
A >> nwill shift all bits except for the signed bit right n times
- Newly introduced bits are the same as the signed bit
10101101 >> 3 == 11110101
Logical Right: »>
A >>> nwill shift ALL bits right n times
- Newly introduced bits are 0
10101101 >>> 3 == 00010101
- Another example:
(-1) >>> 29 == 7because it leaves 3 1-bits- ints are 32 bits
Why is this useful? #
Just looking at these obscure operations, it may be unclear as to why we need to use these at all.
Well, here’s a massive list of bit twiddling hacks that should demonstrate plenty of ways to use these simple operations to do some things really efficiently.
These operations are also the building blocks for almost all operations done by a computer. You’ll see firsthand how these are used to construct CPU’s in 61C.