Java: Numbers, Bits and Strings

Description

Numbers and text are the raw material of nearly every coding problem: counting, summing, indexing into arrays, parsing input, building output. Java handles them in ways that are fast and predictable, but a few of its rules are different from what you might expect from school maths or from other languages. When an interview solution has the right algorithm and still fails a hidden test, one of these rules is usually why.

Here's a small example. A hash table picks a bucket for each key like this:

int bucket(Object key, int buckets) {
    return Math.abs(key.hashCode()) % buckets;
}

It looks safe, since Math.abs makes the number positive. Yet for one particular key it returns -8, and the array lookup that follows crashes. By the end of the "numbers" half of this lesson you'll see exactly why, and the one-word fix.

Here's the path, from easiest to most technical:

1. How big Java's numbers can get, and what happens when they get too big.
2. Division and remainder with negative numbers.
3. Working with bits: shifts and masks.
4. How strings work: why they never change, and how to compare and build them.
5. Characters, emoji, and why a "character" can take two chars.
6. The string methods that surprise people: split and parseInt.

How big can a number get?

Java's int holds whole numbers from about -2.1 billion to about 2.1 billion: exactly -2,147,483,648 to 2,147,483,647. These limits are Integer.MIN_VALUE and Integer.MAX_VALUE. A long holds much bigger numbers, up to about 9.2 quintillion.

The surprise is what happens past the limit. Java doesn't throw an error. The number wraps around to the other end, which is called overflow:

Integer.MAX_VALUE + 1        // -2147483648: wrapped to the most negative int
100_000 * 100_000            // 1410065408: the real answer, 10 billion, doesn't fit
(long) 100_000 * 100_000     // 10000000000: converted to long first, so it fits
(long) (100_000 * 100_000)   // 1410065408: converted after it already wrapped

The last two lines show the most common fix and the most common mistake. Converting to long only helps if you do it before the multiplication. Once an int has wrapped, the damage is done.

There's also one more negative number than positive ones, so the most negative int has no positive twin. That gives you the answer to the bucket puzzle:

-Integer.MIN_VALUE           // -2147483648: still negative
Math.abs(Integer.MIN_VALUE)  // -2147483648: abs can return a negative number

So Math.abs(hash) % buckets can be negative. The fix is Math.floorMod(hash, buckets), which is never negative when buckets is positive. We'll meet it again in the next section.

Four habits keep you safe:

• Widen first. (long) a * b, or ((long) a + b) / 2 for an average.
• Pick a safe "infinity". If you use Integer.MAX_VALUE to mean "unreachable" and later add 1 to it, it turns into a huge negative number that looks like the best answer. Use something like 1,000,000,000 instead (twice it still fits), or skip unreachable values before adding.
• Check before, not after. When you build a number digit by digit, check that the next step won't go past the limit before you take it.
• Fail loudly when you can't be sure. Math.addExact, Math.multiplyExact and Math.toIntExact throw an ArithmeticException instead of wrapping.

One more difference: dividing an integer by zero throws ArithmeticException, but dividing a double by zero gives Infinity (or NaN, "not a number", for 0.0 / 0).

Division and remainder with negative numbers

For positive numbers, / and % work the way you'd expect: 7 / 2 is 3 and 7 % 2 is 1. With negative numbers, Java follows two rules: / rounds toward zero, and the result of % takes the sign of the number on the left.

-7 / 2                // -3: rounded toward zero, not down to -4
-7 % 2                // -1: negative, because -7 is negative
7 % -2                // 1
Math.floorDiv(-7, 2)  // -4: rounds down instead
Math.floorMod(-7, 2)  // 1: never negative for a positive divisor

This bites in two everyday places:

• Odd-number checks. n % 2 == 1 is false for -3, because -3 % 2 is -1. Write n % 2 != 0 instead.
• Walking backwards around a circle. For a carousel of n items, (i - 1) % n gives -1 when i is 0. Write Math.floorMod(i - 1, n) or (i - 1 + n) % n.

Working with bits

Bit tricks show up in interviews for subsets, flags and fast arithmetic. Java has two right shifts, and they differ only for negative numbers:

-8 >> 1          // -4: ">>" keeps the sign
-8 >>> 1         // 2147483644: ">>>" fills with zeros, so the result is a huge positive number
-7 >> 1          // -4: ">>" rounds down, while -7 / 2 is -3
1 << 31          // -2147483648: the top bit is the sign bit
1 << 32          // 1, not 0: Java only uses the last 5 bits of the shift distance
1L << 32         // 4294967296: use a long for bit 32 and up

Two traps follow from this. A loop over all subsets, for (int mask = 0; mask < (1 << n); mask++), runs only once when n is 32, because 1 << 32 is 1. And a flag test needs its parentheses: (flags & MASK) != 0 works, but without them Java reads flags & (MASK != 0), which doesn't compile.

You rarely need to write bit loops by hand. Integer.bitCount(x) counts the 1 bits, Integer.numberOfTrailingZeros(x) finds the lowest set bit, and Integer.toBinaryString(x) shows you the bits while debugging.

Strings never change

A Java String is immutable: once created, it can never change. Methods like toUpperCase or replace give you a new string and leave the original alone.

That has a cost when you build text in a loop:

String s = "";
for (int i = 0; i < n; i++) s = s + i;      // copies the whole string every time: O(n^2)

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i);   // grows one buffer: O(n) overall
String result = sb.toString();

StringBuilder is the tool for building strings piece by piece. One catch: sb.insert(0, x) shifts everything already in the buffer, so prepending in a loop is O(n^2) again. Append everything, then call reverse() once.

Comparing strings: always equals. == asks whether two variables point at the very same object, not whether the text matches. It sometimes seems to work, because Java reuses one object for identical string literals:

String a = "a";
("a" + "b") == "ab"       // true: two literals, joined by the compiler into the same object
(a + "b") == "ab"         // false: built while running, so it's a new object
(a + "b").equals("ab")    // true: same text

Use a.equals(b), or Objects.equals(a, b) when either could be null.

Characters and emoji

A char is really a small number. That's why c - 'a' gives you a letter's position in the alphabet, and 'a' + 1 is 98.

Each char holds one 16-bit piece of text in an encoding called UTF-16. Ordinary letters, digits and most of the world's scripts fit in one char. Characters beyond that, including almost all emoji, take two chars, called a surrogate pair:

"👍".length()                        // 2: length() counts chars, not characters
"👍".codePointCount(0, "👍".length())  // 1: one real character (a "code point")
new StringBuilder("a👍").reverse()    // "👍a": StringBuilder knows to keep the pair together

So code that walks a string one char at a time can cut an emoji in half: swapping chars to reverse a string, cutting at substring(0, n), or counting letters for an anagram check. When text can contain emoji, work with code points: s.codePoints() gives you whole characters.

A related trap: Character.isDigit says yes to digits from every script, including the Arabic-Indic three '٣', and '٣' - '0' is 1587, not 3. For parsing plain numbers, check c >= '0' && c <= '9'.

The string methods that surprise people

split takes a regular expression (a pattern language where some characters have special meaning), not plain text:

"1.2.3".split(".")              // []: in a regex, "." means "any character"
"1.2.3".split("\\.")            // [1, 2, 3]: escape it
"a,b,,".split(",")              // [a, b]: trailing empty pieces are dropped
"a,b,,".split(",", -1)          // [a, b, , ]: a negative limit keeps them
"  hello world  ".split("\\s+") // [, hello, world]: leading spaces leave an empty first piece
"a  b".split(" ")               // [a, , b]: two spaces make an empty piece between them

The same goes for |, +, * and ?: escape them with \\, or use Pattern.quote. Call trim() (or strip()) before splitting user input.

Integer.parseInt is strict:

Integer.parseInt("42")          // 42
Integer.parseInt(" 42")         // NumberFormatException: no spaces allowed
Integer.parseInt("2147483648")  // NumberFormatException: too big for an int

That strictness is what you want when validating input. It's the opposite of the forgiving atoi from the classic interview problem, which skips spaces and clamps big numbers to the limit.

Common mistakes

Check yourself

Try to answer before opening each one. Recalling beats re-reading.

1. Why can Math.abs(h) % n be negative, and what's the fix?

2. What do -7 / 2, -7 % 2 and -7 >> 1 give?

3. A message is "Hi 👋". What does length() return, and why might substring(0, 4) be a problem?

4. What does "a,b,,".split(",") return, and how do you keep the empty fields?

Key takeaways

• Java integers wrap around silently. Widen to long before the operation, pick a safe "infinity", or use Math.addExact and friends.
• Integer.MIN_VALUE has no positive twin, so abs and negation leave it negative.
• / rounds toward zero and % follows the left side's sign. Use Math.floorMod for anything used as an index.
• >> keeps the sign and >>> doesn't; shift distances wrap at 32; put parentheses around & tests.
• Strings never change: compare them with equals and build them with StringBuilder.
• A char isn't always a whole character. Use code points when emoji are possible.
• split takes a regex and drops trailing empties; parseInt is strict.