按位运算符简单地翻转整数中的所有位？

Question

我必须翻转整数的二进制表示形式中的所有位。给定：

10101

输出应该是

01010

当与整数一起使用时，完成此操作的按位运算符是什么？例如，如果我正在编写像 int FlipBits(int n); 这样的方法，那么主体中会包含什么？我只需要翻转数字中已经存在的内容，而不是整数中的所有 32 位。

Answer 1

~ 一元运算符是按位求反。如果您需要的位数少于 int 所容纳的位数，那么您需要在事后用 & 屏蔽它。

Answer 2

只需使用按位非运算符~即可。

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

Answer 3

有多种方法可以使用操作来翻转所有位

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

Answer 4

更快更简单的解决方案：

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

Answer 5

好吧，因为到目前为止，只有一个解决方案可以给出“正确”的结果，而这确实不是一个好的解决方案（使用字符串来计算前导零？这会在我的梦想中困扰我;））

所以这里我们使用一个不错的干净解决方案应该有效 - 虽然还没有彻底测试它，但你明白了要点。确实，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;
}

Answer 6

一条线解决方案

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

Answer 7

如果您只想翻转整数中“使用”的位，请尝试以下操作：

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

Answer 8

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

一行（在 Javascript 中 - 您可以转换为您最喜欢的编程语言）

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

解释：

 10 == ~21 & mask

mask ：用于过滤掉有效位计数之前的所有前导位（nBits - 见下文）

如何计算有效位算不算？

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

例如：

0000000001 返回 1

0001000001 返回 7

0000010101 返回 5

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

Answer 9

我必须看一些例子才能确定，但​​由于二进制补码运算，您可能会得到意想不到的值。如果数字有前导零（如 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 对这个问题的回答也可能有帮助

Answer 10

我有另一种方法来解决这种情况，

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位处理。

Answer 11

由于我们只需要翻转整数所需的最少位（假设 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;
        }

Answer 12

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

Answer 13

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 代码如何解释为机器代码......

Answer 14

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

Answer 15

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

Answer 16

可以通过一个简单的方法来完成，只需从值中减去数字即可
当所有位都等于 1 时获得。
例如：
号码：给定号码
值：所有位都设置为给定数字的数字。
翻转的数字 = 值 – 数字。
例子 ：
数量 = 23,
二进制形式：10111
翻转数字后的数字将为：01000
值：11111 = 31

我们可以在 O(1) 时间内找到固定大小整数的最高有效设置位。为了
下面的代码示例适用于 32 位整数。

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