Binary foundations

Binary is base 2: the digit at position i is worth 2^i. So 1011₂ = 8 + 0 + 2 + 1 = 11. Hexadecimal is base 16 and uses 0-9 and A-F. One hex digit is exactly four bits, so hex is a compact way to write binary: 0x2F = 0010 1111₂ = 47.

Java writes hexadecimal literals with 0x, binary with 0b, and allows underscores: 0xFF, 0b1010_1100, 1_000_000.

1int a = 0b1011;                    // 11
2int b = 0x2F;                      // 47
3int c = 0xFF;                      // 255
4System.out.println(Integer.toBinaryString(47));   // 101111
5System.out.println(Integer.toHexString(255));     // ff
6System.out.println(Integer.parseInt("101111", 2)); // 47

Java stores signed integers in two's complement. In an n-bit value the top bit has weight -2^(n-1), and the other bits have their usual positive weights. So 1111 1011 in 8 bits is -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5.

To negate a number, invert every bit and add 1. That is why -x == ~x + 1. Try 5, then -5, and then -128 in the animation: -128 has no positive partner, so negating it gives -128 again. In Java Integer.MIN_VALUE behaves the same, and so does Math.abs(Integer.MIN_VALUE).

1int negate(int x) {
2    return ~x + 1;                    // invert every bit, then add one
3}

Bits are numbered from the right, starting at 0. The rightmost bit is the least significant bit (LSB), and the leftmost the most significant bit (MSB). Bit i has the value 2^i, which Java writes as 1 << i.

To check which positions are set in 44 = 0010 1100₂: bits 2, 3 and 5. Each animation in this chapter labels the position under every bit.

A mask is an integer used to select or change particular bits with &, | and ^. A single-bit mask is 1 << i. A mask for the lowest k bits is (1 << k) - 1. For example (1 << 4) - 1 = 0b1111 = 15.

Constants like 0xFF (the low 8 bits) and 0x0F (the low 4 bits) are masks. x & 0xFF extracts the low byte of x, which is how you read an unsigned byte value from a signed byte.

1int lowByte  = x & 0xFF;                 // keep the lowest 8 bits
2int upper    = (x >>> 8) & 0xFF;         // the next 8 bits
3int lowBits  = x & ((1 << k) - 1);       // keep the lowest k bits (x mod 2^k)
4int unsigned = someByte & 0xFF;          // byte -56 -> 200

To convert decimal to binary, divide by 2 repeatedly and collect the remainders; the first remainder is the lowest bit. Reading them in reverse gives the binary number. The animation shows the remainders arriving lowest bit first and then the reversed result.

To convert back, add 2^i for each set bit, or use Horner's rule: start at 0 and for each bit from the left do value = value * 2 + bit. Java does both for you with Integer.toBinaryString and Integer.parseInt(s, 2).

1static int fromBinary(String s) {
2    int value = 0;
3    for (char c : s.toCharArray()) {
4        value = value * 2 + (c - '0');     // Horner's rule
5    }
6    return value;
7}

1static String toBinary(int n) {
2    if (n == 0) return "0";
3    StringBuilder sb = new StringBuilder();
4    while (n > 0) {
5        sb.append(n % 2);                // the remainder is the next bit, lowest first
6        n /= 2;
7    }
8    return sb.reverse().toString();
9}

Java's integer types have fixed widths: byte 8 bits, short 16, int 32, long 64, and char is an unsigned 16 bits. A value that does not fit wraps around: (byte) 200 is -56, and Integer.MAX_VALUE + 1 is Integer.MIN_VALUE.

Fixed width matters in bit tricks: ~x flips all 32 bits of an int, and x << 33 shifts by 33 & 31 = 1 because the shift distance is taken modulo the width.

1byte b = (byte) 200;                    // -56 (200 - 256)
2int wrapped = Integer.MAX_VALUE + 1;    // -2147483648
3int shift = 1 << 33;                    // 2, because 33 & 31 == 1
4long big = 1L << 40;                    // use 1L, not 1, for shifts beyond 31