Topics › Bit Manipulation › Learn Bit Manipulation

Check if a Number is Odd or Not

Easy TUF ID 171 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer n. Return true if n is odd and false if it is even. Zero is even, and negative numbers follow the usual definition: -3 is odd, -4 is even.

Constraints: n is any 32-bit signed integer, -2^31 ≤ n ≤ 2^31 - 1.

Example 1

n = 7
answer = true        // 7 = 2 * 3 + 1

Example 2

n = 10
answer = false       // 10 = 2 * 5

Example 3

n = -3
answer = true        // -3 = 2 * (-2) + 1; a common bug reports this as even

The problem is tiny, but it is the first place where the arithmetic view of a number and the bit view line up, and the trap in Example 3 is worth understanding once so that it never bites again.

Approach 1: Remainder on division by 2

Intuition. A number is even when dividing it by 2 leaves nothing over, so test the remainder. The only subtlety is what Java’s % returns for negative numbers: the remainder takes the sign of the dividend, so -3 % 2 is -1, not 1. Comparing the remainder with 0 sidesteps the issue; comparing it with 1 does not.

Algorithm.

1. Compute n % 2.
2. Return whether it differs from 0.

static boolean usingModulo(int n) {
    return n % 2 != 0;
}

Complexity. Time O(1), one division. Space O(1).

The buggy variant is kept in the Java file so the test can prove the point:

static boolean naiveModuloEqualsOne(int n) {
    return n % 2 == 1;
}

naiveModuloEqualsOne(3) is true but naiveModuloEqualsOne(-3) is false. Any solution that compares a remainder with a positive constant has to assume a non-negative input.

Approach 2: Divide, multiply back, compare

Intuition. Integer division throws away the fractional part. n / 2 * 2 rebuilds the largest even number that is at most |n| in magnitude; it equals n only when nothing was thrown away, that is, when n was even. This version has no sign problem because truncation toward zero is symmetric: -3 / 2 = -1, -1 * 2 = -2 ≠ -3.

Algorithm.

1. Compute n / 2 * 2 (left to right, so the division happens first).
2. Return whether it differs from n.

static boolean usingDivision(int n) {
    return n / 2 * 2 != n;
}

Complexity. Time O(1), space O(1).

This is rarely written in practice, but it is the arithmetic twin of the bit trick below: “clear the lowest bit, then compare” is exactly what dividing by 2 and multiplying back does.

Approach 3: Optimal, look at the lowest bit

Intuition. Write n in binary: n = b_31 · 2^31 + ... + b_1 · 2 + b_0. Every term except the last is a multiple of 2, so the parity of n is the parity of b_0. The number is odd if and only if its lowest bit is 1. n & 1 keeps only that bit.

This also holds for negative numbers in two’s complement, because the top bit has weight -2^31, which is still even. -3 is ...11111101 and its lowest bit is 1; -4 is ...11111100 and its lowest bit is 0.

Algorithm.

1. Compute n & 1.
2. Return whether it equals 1.

static boolean usingBitwiseAnd(int n) {
    return (n & 1) == 1;
}

Dry run.

Complexity. Time O(1), a single AND, which is cheaper than a division on every CPU. Space O(1).

Modern compilers turn n % 2 != 0 into the same AND instruction, so the gain is in clarity of intent rather than speed: n & 1 says “I am looking at the lowest bit”, and it cannot be written with the wrong comparison the way % 2 == 1 can.

Generalising: the low k bits

The reason n & 1 works is that the low k bits of n are n mod 2^k. The mask (1 << k) - 1 is k ones, and AND-ing with it extracts that remainder:

static int lowBits(int n, int k) {
    return n & ((1 << k) - 1);
}

For negative n this gives the mathematician’s non-negative residue, where % gives a negative one: lowBits(-6, 2) is 2 because -6 = -8 + 2, while -6 % 4 is -2. Divisibility by a power of two is then “all low bits are zero”:

static boolean isDivisibleByPowerOfTwo(int n, int k) {
    return (n & ((1 << k) - 1)) == 0;
}

40 = 101000 has three trailing zeros, so it is divisible by 8; 12 = 1100 has two, so it is divisible by 4 but not 8. Replacing % 8 == 0 with & 7 == 0 is the same idea as this whole article, one bit wider.

Edge cases and pitfalls

• Zero. 0 % 2, 0 / 2 * 2 and 0 & 1 are all 0, so every approach reports even.
• Negative odd numbers. n % 2 == 1 fails on them. Compare with 0, use Math.floorMod(n, 2) == 1, or use n & 1.
• Integer.MIN_VALUE. -2^31 is even; n & 1 is 0 and n % 2 is 0. Integer.MAX_VALUE is 2^31 - 1, odd, and n & 1 is 1.
• Precedence. n & 1 == 1 parses as n & (1 == 1), which does not compile in Java because & between int and boolean is not defined. Always write (n & 1) == 1.
• Floating point. None of this applies to double; 2.5 is neither odd nor even and % on doubles is a different operation.

Related problems

• Introduction to Bits and Tricks explains two’s complement, which is why the bit test works on negatives.
• Check if the i-th bit is Set or Not generalises from bit 0 to bit i.
• Check if a Number is Power of 2 or Not is the next one-line test built on n & (n - 1).
• Count the Number of Set Bits adds up n & 1 while shifting.