☕ DSA Java Articles

Topics › Bit Manipulation › Learn Bit Manipulation

Introduction to Bits and Tricks

Easy TUF ID 1155 A2Z

Java source ↗ Edit this article ↗

What this covers

Every int in Java is 32 bits, every long is 64, and the CPU can AND, OR, XOR, invert and shift those bits in a single instruction. Bit manipulation is the habit of using those instructions directly instead of going through arithmetic. The payoff is small constant factors in ordinary code and, more importantly, a set of identities that make some problems trivial: finding the element that appears once, testing for a power of two, iterating over all subsets of a set. This article builds the toolbox from the ground up: how numbers are written in binary, how negatives are stored, what each operator does, and the ten or so one-line tricks that every later problem in this section reuses. Each snippet is a method in the Java file, and main checks all of them against the library.

Binary representation and conversion

A number written in base 2 is a sum of powers of two. 13 = 8 + 4 + 1 = 1101 in binary: bit 3, bit 2 and bit 0 are set, bit 1 is not. We number bits from the right starting at 0, so bit i has weight 2^i. The rightmost bit is the least significant bit (LSB) and the leftmost the most significant bit (MSB).

To convert a non-negative decimal to binary, divide by 2 repeatedly and record the remainders. Each remainder is the next bit from the right, so the digits come out reversed:

static String toBinary(int n) {
    if (n == 0) return "0";
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        sb.append(n % 2);
        n /= 2;
    }
    return sb.reverse().toString();
}

For 13: 13 % 2 = 1, 6 % 2 = 0, 3 % 2 = 1, 1 % 2 = 1, giving 1011 which reversed is 1101. The loop runs once per bit, so O(log n).

Going back is Horner’s rule: start with 0 and, for each digit from the left, double what you have and add the digit. Doubling shifts everything collected so far one position left to make room:

static int fromBinary(String s) {
    int value = 0;
    for (int i = 0; i < s.length(); i++) {
        value = value * 2 + (s.charAt(i) - '0');
    }
    return value;
}

s.charAt(i) - '0' converts the character '1' to the integer 1; forgetting the subtraction and adding the character code 49 is a classic mistake.

Negative numbers: one’s and two’s complement

toBinary above only handles n ≥ 0, because negative numbers are not stored with a minus sign. Java (like every mainstream CPU) uses two’s complement: the top bit has weight -2^31 instead of +2^31. So -1 is all 32 bits set (-2^31 + (2^31 - 1) = -1), Integer.MIN_VALUE is a single 1 followed by 31 zeros, and Integer.MAX_VALUE is a 0 followed by 31 ones. Printing all 32 positions makes this visible:

static String toBinary32(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 31; i >= 0; i--) {
        sb.append(((n >> i) & 1) == 1 ? '1' : '0');
    }
    return sb.toString();
}

The recipe for negating a number explains the name. One’s complement flips every bit, which Java spells ~n. Two’s complement adds one to that. Flipping every bit of n gives -1 - n (because n + ~n is all ones, which is -1), so ~n + 1 = -n:

static int onesComplement(int n) {
    return ~n;
}

static int twosComplement(int n) {
    return ~n + 1;
}

The tests confirm twosComplement(n) == -n for every value tried, including Integer.MIN_VALUE, whose negation does not fit in an int and wraps back to itself. Two facts that follow from this representation and that the tricks below depend on: ~n == -n - 1, and -n agrees with n in exactly one bit, the lowest set bit, with everything above it inverted.

The operators

Java has six bitwise operators on integers. The first four work position by position:

Operator Name Rule per bit 12 = 1100 with 10 = 1010
a & b AND 1 only if both are 1 1000 = 8
a \| b OR 1 if at least one is 1 1110 = 14
a ^ b XOR 1 if exactly one is 1 0110 = 6
~a NOT flip ~1100 = ...10011 = -13

AND is a mask: n & m keeps only the bits of n where m has a 1. OR turns bits on. XOR toggles the bits where the mask has a 1, and XOR-ing twice with the same mask undoes itself. NOT on an int always flips all 32 bits, which is why ~12 is a negative number and not 0011 = 3.

The last two operators are shifts. n << k moves every bit k places left and fills with zeros, which multiplies by 2^k:

static int multiplyByPowerOfTwo(int n, int k) {
    return n << k;
}

n >> k moves bits right and fills the vacated top positions with copies of the sign bit, so negative numbers stay negative. This is division by 2^k that rounds toward negative infinity, which is not what / does for negatives: -7 >> 1 is -4 but -7 / 2 is -3.

static int divideByPowerOfTwo(int n, int k) {
    return n >> k;
}

The sixth operator, >>>, is the unsigned right shift: it fills with zeros regardless of sign. -1 >>> 28 is 15, because the all-ones pattern is treated as the unsigned number 2^32 - 1. Use >>> when you want to walk over the bits of a possibly negative number until it becomes zero; with >> a negative number never reaches zero.

Two things to remember about shifts in Java. The shift amount is taken modulo 32 for int and 64 for long, so 1 << 32 is 1, not 0. And 1 << 31 is Integer.MIN_VALUE: the 1 lands on the sign bit. If you need the long 2^31, write 1L << 31.

The tricks

Every one of these is one line, and every one has a short reason that makes it unforgettable.

Parity. Of all the powers of two only 2^0 = 1 is odd, so n is odd exactly when bit 0 is set. This works for negatives too, unlike n % 2 == 1, which is false for -3 because -3 % 2 is -1 in Java.

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

Power of two. A power of two is a lone 1 bit. Subtracting 1 turns that bit off and every bit below it on, so n & (n - 1) is zero precisely when there was nothing above the lowest set bit. The n > 0 guard rejects 0 (where 0 & -1 == 0) and negatives.

static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Reading, setting, clearing and toggling bit i. Build the mask 1 << i and apply the right operator. To read a bit you can either AND with the mask and compare to zero, or shift the bit down to position 0 and AND with 1.

static boolean isBitSet(int n, int i) {
    return ((n >> i) & 1) == 1;
}

static int setBit(int n, int i) {
    return n | (1 << i);
}

static int clearBit(int n, int i) {
    return n & ~(1 << i);
}

static int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

The lowest set bit. n - 1 flips the lowest set bit and all the zeros below it, and nothing else. AND-ing with n therefore removes exactly that bit. Separately, -n = ~n + 1 has the same lowest set bit as n with everything above inverted, so n & -n keeps only that bit.

static int removeLowestSetBit(int n) {
    return n & (n - 1);
}

static int lowestSetBit(int n) {
    return n & -n;
}

On 12 = 1100: 12 & 11 = 1100 & 1011 = 1000 = 8, and 12 & -12 = 1100 & ...0100 = 100 = 4.

Counting set bits. Repeat “remove the lowest set bit” until nothing is left; the number of rounds is the popcount. This is Brian Kernighan’s algorithm and it runs in time proportional to the number of ones rather than the number of bits. Integer.bitCount does the same job with a hardware instruction.

static int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

XOR properties

XOR deserves its own section because so many problems reduce to two facts: x ^ x == 0 and x ^ 0 == x, together with the fact that XOR is commutative and associative, so the order in which you XOR a collection does not matter.

The first consequence is a swap without a temporary variable. After a ^= b, a holds a0 ^ b0. Then b ^= a gives b = b0 ^ a0 ^ b0 = a0, and a ^= b gives a = a0 ^ b0 ^ a0 = b0.

static int[] swapWithXor(int a, int b) {
    a ^= b;
    b ^= a;
    a ^= b;
    return new int[]{a, b};
}

The second is cancellation. XOR every element of an array in which all values but one appear an even number of times, and the pairs annihilate, leaving the odd one out. No sorting, no hash map, O(n) time and O(1) space.

static int oddOneOut(int[] a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

Pitfalls