Bitwise operator for simply flipping all bits in an integer?

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 a开发者_如何转开发ccomplish 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.

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.

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

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;

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

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

One Line Solution

int flippingBits(int n) {
   return n ^ ((1 << 31) - 1);
}

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

I have another way to solve this case,

public static int complementIt(int c){
 return c ^ (int)(Math.pow(2, Math.ceil(Math.log(c)/Math.log(2))) -1);
}

It is using XOR to get the complement bit, to complement it we need to XOR the data with 1, for example :

101 XOR 111 = 010

(111 is the 'key', it generated by searching the 'n' square root of the data)

if you are using ~ (complement) the result will depend on its variable type, if you are using int then it will be process as 32bit.

As we are only required to flip the minimum bits required for the integer (say 50 is 110010 and when inverted, it becomes 001101 which is 13), we can invert individual bits one at a time from the LSB to MSB, and keep shifting the bits to the right and accordingly apply the power of 2. The code below does the required job:

int invertBits (int n) {
        int pow2=1, int bit=0;
            int newnum=0;
            while(n>0) {
              bit = (n & 1);
              if(bit==0)
                  newnum+= pow2;
              n=n>>1;
              pow2*=2;
          }
          return newnum;
        }

import java.math.BigInteger;
import java.util.Scanner;

public class CodeRace1 {

    public static void main(String[] s) {
        long input;
        BigInteger num,bits = new BigInteger("4294967295");
        Scanner sc = new Scanner(System.in);
        input = sc.nextInt();
        sc.nextLine();
        while (input-- > 0) {
            num = new BigInteger(sc.nextLine().trim());
            System.out.println(num.xor(bits));
        }
    }
}

The implementation from openJDK, Integer.reverse():

public static int More ...reverse(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

Base on my experiments on my laptop, the implementation below was faster:

public static int reverse2(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
    i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;

    return i;
}

Not sure what's the reason behind it - as it may depends on how the java code is interpreted into machine code...

If you just want to flip the bits which are "used" in the integer, try this:

public int flipBits(int n) {
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}

public static int findComplement(int num) {
    return (~num & (Integer.highestOneBit(num) - 1));
}

int findComplement(int num) {
        int i = 0, ans = 0;
        while(num) {
            if(not (num & 1)) {
                ans += (1 << i);
            }
            i += 1;
            num >>= 1;
        }
        return ans;
}

          Binary 10101 == Decimal 21
  Flipped Binary 01010 == Decimal 10

One liner (in Javascript - You could convert to your favorite programming language )

10 == ~21 & (1 << (Math.floor(Math.log2(21))+1)) - 1

Explanation:

 10 == ~21 & mask

mask : For filtering out all the leading bits before the significant bits count (nBits - see below)

How to calculate the significant bit counts ?

Math.floor(Math.log2(21))+1   => Returns how many significant bits are there (nBits)

Ex:

0000000001 returns 1

0001000001 returns 7

0000010101 returns 5

(1 << nBits) - 1         => 1111111111.....nBits times = mask

It can be done by a simple way, just simply subtract the number from the value obtained when all the bits are equal to 1 . For example: Number: Given Number Value : A number with all bits set in a given number. Flipped number = Value – Number. Example : Number = 23, Binary form: 10111 After flipping digits number will be: 01000 Value: 11111 = 31

We can find the most significant set bit in O(1) time for a fixed size integer. For example below code is for a 32-bit integer.

int setBitNumber(int n)
{
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
n = n + 1;
return (n >> 1);
}