我必须以整数的二进制表示形式翻转所有位。鉴于：
10101
输出应该是
01010
与整数一起使用时，实现此操作的按位运算符是什么？例如，如果我正在编写像int flipBits(int n);这样的方法，身体会发生什么？我只需要翻转数字中已经存在的内容，而不是整数中的所有32位。
~一元运算符是按位否定。如果你需要比int更少的位，那么你需要在事后用&掩盖它。
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;
}
public static int findComplement(int num) {
return (~num & (Integer.highestOneBit(num) - 1));
}
你可以试试这个：
/**
* 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.");
}
}
样本输出：
原始数字是十进制21，二进制10101 十进制翻转数为10，二进制为01010 翻转位后21变为10。
只需使用按位非运算符~。
int flipBits(int n) {
return ~n;
}
要使用k个最低有效位，请将其转换为右掩码。 （我假设你至少需要1位，这就是掩码从1开始的原因）
int flipBits(int n, int k) {
int mask = 1;
for (int i = 1; i < k; ++i)
mask |= mask << 1;
return ~n & mask;
}
正如Lưu Vĩnh Phúc所建议的那样，可以将面具创建为(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;
好吧，因为到目前为止只有一个解决方案给出了“正确”的结果，而且......真的不是一个很好的解决方案（使用字符串计算前导零？这会困扰我的梦想;））
所以在这里我们采用一个很好的清洁解决方案应该可以工作 - 虽然没有彻底测试，但你得到了要点。真的，没有无符号类型的java对于这类问题非常讨厌，但它应该是非常有效的（并且如果我可以说比创建字符串中的字符串更优雅）
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;
}
更快更简单的解决方案：
/* 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;
}
我必须看到一些例子可以确定，但是由于二进制补码运算，你可能会得到意想不到的值。如果数字具有前导零（如在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;
}
我现在没有设置java环境来测试它，但这是一般的想法。基本上只是将数字转换为字符串，切断前导零，翻转位，然后将其转换回数字。 Integer类甚至可以通过某种方式将字符串解析为二进制数。我不知道问题是否需要完成，它可能不是最有效的方法，但它会产生正确的结果。
编辑：polygenlubricants对this question的回答也许有帮助
我有另一种解决这种情况的方法，
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是'关键'，它是通过搜索数据的'n'平方根生成的）
如果你使用〜（补码），结果将取决于它的变量类型，如果你使用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));
}
}
}