位运算符简单地翻转一个整数的所有位？
我必须翻转整数的二进制表示中的所有位。 鉴于：
10101 输出应该是
01010
什么是按位运算符来完成此与整数一起使用？ 例如，如果我正在写像int flipBits(int n); ，身体会发生什么？ 我只需要翻转已经存在的数字，而不是整数中的所有32位。
~一元运算符是按位否定。 如果你需要的位数比int那么你需要用&掩盖它。
只需使用按位不操作符~ 。
int flipBits(int n) { return ~n; }
编辑：使用k最低有效位，将其转换为正确的掩码。 （我假设你至less需要1位，这就是为什么mask从1开始）
int flipBits(int n, int k) { int mask = 1; for(int i = 1; i < k; ++i) mask |= mask << 1; return ~n & mask; }
Edit2：刚才看到这个问题是Java的..认为它的C！ 编辑它。
Edit3：正如LưuVĩnhPhúc所build议的那样，我们可以将掩码创build为(1 << k) - 1而不是使用循环。
int flipBits2(int n, int k) { int mask = (1 << k) - 1; return ~n & mask; }
有很多方法可以使用操作来翻转所有的位
x = ~x; // has been mentioned and the most obvious solution. x = -x - 1; or x = -1 * (x + 1); x ^= -1; or x = x ^ ~0;
那么到目前为止，只有一个解决scheme给出了“正确”的结果，这真的不是一个很好的解决scheme（使用一个string来计算前导零点，这将在我的梦中困扰着我）
所以在这里，我们要一个很好的干净的解决scheme，应该工作 – 虽然没有testing它，但你得到的主旨。 实际上，没有unsignedtypes的java对于这类问题是非常烦人的，但是它应该是非常有效的（如果我可以这么说，比创build一个string更优雅）
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; }
更快，更简单的解决scheme：
/* 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; }
我必须看到一些例子是可以肯定的，但是由于二进制补码algorithm，你可能会得到意想不到的值。 如果这个数字有前导零（就像在26的情况下那样），〜运算符会翻转这些数字使它们成为前导零 – 导致一个负数。
一种可能的解决方法是使用Integer类：
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; }
我现在没有build立一个Java环境来testing它，但这是一般的想法。 基本上只是将数字转换为一个string，切断前导零，翻转位，并将其转换回数字。 Integer类甚至可以用一些方法将stringparsing成二进制数。 我不知道这是怎么回事，可能不是最有效的方法，但会产生正确的结果。
编辑：polygenlubricants' 这个问题的答案也可能是有帮助的
我有另一种方法来解决这个案子，
public static int complementIt(int c){ return c ^ (int)(Math.pow(2, Math.ceil(Math.log(c)/Math.log(2))) -1); }
它使用XOR来获得补码位，为了补充它，我们需要用1来异或数据，例如：
101 XOR 111 = 010
（111是“键”，它是通过search数据的“n”平方根产生的）
如果你正在使用〜（补），结果将取决于它的variablestypes，如果你使用int，那么它将被处理为32位。
由于我们只需要翻转整数所需的最小位（比如说50是110010，当它翻转时，它变成001101就是13），我们可以一次一个地从LSB到MSB反转单独的位，位右移，相应地应用2的幂。下面的代码完成所需的工作：
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)); } } }
从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; }
根据我在笔记本电脑上的实验，下面的实现速度更快：
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; }
不知道背后的原因是什么 – 因为它可能取决于如何将java代码解释为机器代码…
如果你只是想翻转在整数“使用”的位，试试这个：
public int flipBits(int n) { int mask = (Integer.highestOneBit(n) << 1) - 1; return n ^ mask; }
实现翻转位的简单代码：
#include<stdio.h> main() { unsigned x = 5; printf("%u",~x); }
