Bitwise operator for simply flipping all bits in a

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.

Answer 1

Simple code to implement the flipping bits:

#include<stdio.h>

main() {
    unsigned x = 5;
    printf("%u",~x);
}

Answer 2

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;
}

Answer 3

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.

Answer 4

You can try this:

/**
 * Flipping bits of a decimal Integer.
 */
public class FlipBits {

    public static final char ONE_CHAR = '1';
    public static final char ZERO_CHAR = '0';

    static int flipBits(int n) {
        String nBinary = Integer.toBinaryString(n);
        System.out.println("Original number is decimal " + n + ", and binary  " + nBinary);
        char[] result = new char[nBinary.length()];
        char[] nBinaryChars = nBinary.toCharArray();
        for (int i = 0; i < nBinaryChars.length; i++) {
            result[i] = nBinaryChars[i] == ONE_CHAR ? ZERO_CHAR : ONE_CHAR;
        }
        int resultDecimal = Integer.parseInt(String.valueOf(result), 2);
        System.out.println("Flipped number in decimal is " + resultDecimal
                + ", and in binary is " + String.valueOf(result));
        return resultDecimal;
    }

    public static void main(String[] args) {
        int input = 21;
        int flippedInteger = flipBits(input);
        System.out.println(input + " becomes " + flippedInteger + " after flipping the bits.");
    }

}

Sample output:

Original number is decimal 21, and binary 10101
Flipped number in decimal is 10, and in binary is 01010
21 becomes 10 after flipping the bits.

Answer 5

I'd have to see some examples to be sure, but you may be getting unexpected values because of two's complement arithmetic. If the number has leading zeros (as it would in the case of 26), the ~ operator would flip these to make them leading ones - resulting in a negative number.

One possible workaround would be to use the Integer class:

int flipBits(int n){
    String bitString = Integer.toBinaryString(n);
    int i = 0;

    while (bitString.charAt(i) != '1'){
        i++;
    }

    bitString = bitString.substring(i, bitString.length());

    for(i = 0; i < bitString.length(); i++){
        if (bitString.charAt(i) == '0')
            bitString.charAt(i) = '1';
        else
            bitString.charAt(i) = '0';
    }

    int result = 0, factor = 1;

    for (int j = bitString.length()-1; j > -1; j--){
        result += factor * bitString.charAt(j);
        factor *= 2;
    }

    return result;
}

I don't have a java environment set up right now to test it on, but that's the general idea. Basically just convert the number to a string, cut off the leading zeros, flip the bits, and convert it back to a number. The Integer class may even have some way to parse a string into a binary number. I don't know if that's how the problem needs to be done, and it probably isn't the most efficient way to do it, but it would produce the correct result.

Edit: polygenlubricants' answer to this question may also be helpful

Answer 6

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;