Bitwise operator for simply flipping all bits in an integer?

Question

I have to flip all bits in a binary representation of an integer. Given:

10101

The output should be

01010

What is the bitwise operator to accomplish this when used with an integer? For example, if I were writing a method like int flipBits(int n);, what would go in the body? I need to flip only what's already present in the number, not all 32 bits in the integer.

Solution 1

The ~ unary operator is bitwise negation. If you need fewer bits than what fits in an int then you'll need to mask it with & after the fact.

Solution 2

Simply use the bitwise not operator ~.

int flipBits(int n) {
    return ~n;
}

To use the k least significant bits, convert it to the right mask.
(I assume you want at least 1 bit of course, that's why mask starts at 1)

int flipBits(int n, int k) {
    int mask = 1;
    for (int i = 1; i < k; ++i)
        mask |= mask << 1;

    return ~n & mask;
}

As suggested by Lưu Vĩnh Phúc, one can create the mask as (1 << k) - 1 instead of using a loop.

int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return ~n & mask;
}

Solution 3

There is a number of ways to flip all the bit using operations

x = ~x; // has been mentioned and the most obvious solution.
x = -x - 1; or x = -1 * (x + 1);
x ^= -1; or x = x ^ ~0;

Solution 4

faster and simpler solution :

/* inverts all bits of n, with a binary length of the return equal to the length of n
k is the number of bits in n, eg k=(int)Math.floor(Math.log(n)/Math.log(2))+1
if n is a BigInteger : k= n.bitLength();
*/
int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return n ^ mask;
}

Solution 5

Well since so far there's only one solution that gives the "correct" result and that's.. really not a nice solution (using a string to count leading zeros? that'll haunt me in my dreams ;) )

So here we go with a nice clean solution that should work - haven't tested it thorough though, but you get the gist. Really, java not having an unsigned type is extremely annoying for this kind of problems, but it should be quite efficient nonetheless (and if I may say so MUCH more elegant than creating a string out of the number)

private static int invert(int x) {
    if (x == 0) return 0; // edge case; otherwise returns -1 here
    int nlz = nlz(x);
    return ~x & (0xFFFFFFFF >>> nlz);
}

private static int nlz(int x) {
    // Replace with whatever number leading zero algorithm you want - I can think
    // of a whole list and this one here isn't that great (large immediates)
    if (x < 0) return 0;
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000) == 0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        n++;
    }       
    return n;
}

View more solutions