Flip the Bits of a Number in Java

1. Overview

Bit manipulation is a fundamental concept in programming that involves working with individual bits of binary data. One common operation is flipping all bits in an integer, converting every 0 to 1 and every 1 to 0.

In this tutorial, we’ll explain what bit flipping means and explore several Java methods to flip the bits of an integer. For completeness, we’ll cover both full 32-bit flipping and flipping only the significant bits.

2. Understanding Bit Flipping

Before we learn how to flip bits in an integer, it’s best to look at a visual example.

To begin with, let’s consider the decimal number 21 and, more specifically, its binary representation:

10101

The goal is to invert each bit so that every 0 becomes a 1 and every 1 becomes a 0:

01010

This corresponds to the decimal value 10 (8+2).

During this transformation, each bit at position i in the original number gets inverted in the result. However, there’s an important distinction to make. When we flip all 32 bits of an integer, i.e., its full size, the result differs from flipping only the significant bits. For instance, flipping all 32 bits of the integer 21 produces -22 due to two’s complement representation, whereas flipping only the significant bits (10101 -> 01010) yields 10.

In the following sections, let’s explore both scenarios in detail.

3. Using the Bitwise NOT Operator

The most direct approach to flip bits is the bitwise NOT operator ~. This unary operator inverts every bit in the integer’s binary representation:

public static int flipAllBits(int n) {
    return ~n;
}

The operator flips all 32 bits of the integer. This means that ~ inverts every bit, including leading zeros, turning a positive number into a negative one due to the two’s complement representation in Java.

Let’s verify the results using a JUnit 5 test and AssertJ matchers:

@Test
void givenPositiveInteger_whenFlipAllBits_thenReturnsNegativeComplement() {
    assertThat(flipAllBits(21)).isEqualTo(-22);
    assertThat(flipAllBits(0)).isEqualTo(-1);
    assertThat(flipAllBits(-1)).isEqualTo(0);
}

As we can see, flipping all 32 bits of 21 gives us -22, not 10. This is because Java’s int type is a signed 32-bit integer.

To get a result like 10 from 21, we need to flip only the significant bits. Let’s cover this case next.

4. Flipping Only the Significant Bits

In many practical scenarios, we want to flip only the bits that are actually used in the binary representation of the number, excluding leading zeros. For instance, flipping the significant bits of 21 (10101) should give us 10 (01010).

4.1. Using a Mask With Bit Length Calculation

The idea is straightforward: we create a mask with a 1 at each significant bit position, then XOR the number with this mask. The XOR operation flips only the bits where the mask has a 1:

public static int flipSignificantBits(int n) {
    if (n == 0) {
        return 0;
    }
    int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
    int mask = (1 << bitLength) - 1;
    return n ^ mask;
}

First, we handle the edge case where n is 0. Then, we calculate the number of significant bits using Integer.numberOfLeadingZeros(). With this value, we create a mask by shifting 1 left by bitLength positions and subtracting 1, which gives us a sequence of 1s matching the significant bit length.

Finally, the XOR operation (^) flips only the significant bits, since XOR with 1 inverts a bit while XOR with 0 leaves it unchanged.

Let’s verify this with a test:

@Test
void givenPositiveInteger_whenFlipSignificantBits_thenReturnsFlippedValue() {
    assertThat(flipSignificantBits(21)).isEqualTo(10);
    assertThat(flipSignificantBits(26)).isEqualTo(5);
    assertThat(flipSignificantBits(0)).isEqualTo(0);
    assertThat(flipSignificantBits(1)).isEqualTo(0);
    assertThat(flipSignificantBits(7)).isEqualTo(0);
}

To illustrate, let’s trace through the example with 26 (binary 11010):

n     = 11010  (26)
mask  = 11111  (31)
n ^ mask = 00101  (5)

This approach effectively and efficiently flips only the significant bits.

4.2. Using Integer.highestOneBit()

We can also use the built-in Integer.highestOneBit() method to build the mask. This method returns a value with only the highest bit of the input set:

public static int flipSignificantBitsUsingHighestOneBit(int n) {
    if (n == 0) {
        return 0;
    }
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}

Here, Integer.highestOneBit(n) returns the value of the most significant bit. By shifting it left by one position and subtracting 1, we create a mask with a 1 at each significant bit. Then, a XOR operation with this mask again flips only those bits.

4.3. Using the Bitwise NOT With a Mask

Instead of XOR, we can also combine the bitwise NOT operator with a mask to get the same result:

public static int flipSignificantBitsUsingNot(int n) {
    if (n == 0) {
        return 0;
    }
    int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
    int mask = (1 << bitLength) - 1;
    return ~n & mask;
}

This function first computes the bitwise NOT of n, which flips all 32 bits. Then, the AND operation with the mask zeroes out all the bits beyond the significant ones. Simply put, the result is equivalent to flipping only the significant bits.

5. Alternative Methods

Apart from the standard bitwise operators, there are other, more unorthodox ways to flip all 32 bits of an integer.

5.1. Using Arithmetic Negation

Due to the two’s complement representation, flipping all bits of n is equivalent to computing -n – 1:

public static int flipBitsArithmetic(int n) {
    return -n - 1;
}

This works because, in two’s complement, the negation of n is the bitwise complement plus 1 (-n = ~n + 1). Therefore, ~n = -n – 1, which gives the same result as the bitwise NOT operator.

5.2. Using XOR With -1

Another way to flip all bits is to XOR the number with -1. In binary, we represent -1 as all 1s (11111111…1 in 32 bits). Notably, ~0 also evaluates to -1, so we can use either interchangeably:

public static int flipBitsXorMinusOne(int n) {
    return n ^ -1;
}

Since XOR with 1 flips a bit, performing XOR with a value where all bits are 1 effectively flips every bit in the integer. This produces the same result as the ~ operator.

6. Conclusion

In this article, we explored several approaches for flipping bits of an integer in Java. We started with the bitwise NOT operator for full 32-bit flipping. Next, we looked at mask-based methods for flipping only the significant bits using XOR and AND operations. Finally, we covered alternative approaches using arithmetic negation and XOR.

As always, all the source code is available over on GitHub.