用于简单翻转整数中所有位的位运算符是什么？

Question

我需要翻转一个整数的二进制表示中的所有位。已知:

10101

输出应该是：

01010

如果我要写一个像 int flipBits(int n); 这样的方法，使用整数进行按位运算来完成这个操作，需要使用哪个位运算符？我只想翻转数字中已经存在的位，而不是对整个 32 位整数进行翻转。

- Naftuli Kay

---

OP是什么意思：“我只需要翻转数字中已经存在的部分，而不是整个32位整数。”？如果数字是“000101”，他希望得到“111010”还是像“000”那样被“010”跟随，因为第一个从第3个LSB开始？无论哪种方式，“翻转所有位”与之前的陈述不一致。 - Salil

Answer 1

~一元运算符是按位取反操作符。如果您需要的位数比int类型能存储的位数少，那么在运算后您需要使用&进行掩码操作。

- Ignacio Vazquez-Abrams

---

在Scala中怎么样？当我执行~22时，结果完全错误，我期望是9，但实际得到的是-23。 - soMuchToLearnAndShare

刚刚意识到 Scala 默认不支持未赋值的 int 类型，因此它会将所有内容视为有符号数。我猜在执行 ~ 操作后，需要左移一位来得到 Java 或人眼所期望的结果。 - soMuchToLearnAndShare

@soMuchToLearnAndShare 我也遇到了同样的问题（对我来说是在 Rust 中），我不得不按照字符串长度进行位移（请参见此处：https://stackoverflow.com/a/71248916/12069968）。 - Jake Ireland

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

- George

---

不幸的是，这并没有给我期望的值。26的位反转应该是11，但是当使用~时，我得到了一些疯狂的值。有没有办法让它只使用整数中实际使用的位数？ - Naftuli Kay

在Java中，int始终是32位（2的补码），无论所表示的数字大小如何。 - Reese Moore

顺便提一下，26的按位反转不是11，而是5。26的二进制表示为11010，取反后得到00101，即为5。 - George

为了获得k个低位设置为1的掩码，请使用(1 << k) - 1，而不是循环并设置每个位。 - phuclv

你说得对，这似乎是一种更好的方法。编辑了答案以包含你的建议。 - George

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;

- Peter Lawrey

Answer 4

由于目前只有一种解决方案能够给出“正确”的结果，而那个解决方案并不是很好（使用字符串来计算前导零？那会在我的梦中萦绕着我；）

所以，我们来看一个漂亮干净的解决方案，应该可以工作-虽然我没有彻底测试过，但你可以理解。实际上，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;
}

- Voo

Answer 5

更快、更简单的解决方案：

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

- serge boisse

Answer 6

一行解决方案

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

- Vaibhav Pratihar

Answer 7

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

一行代码（使用JavaScript编写 - 您可以将其转换为您喜欢的编程语言）

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

解释：

 10 == ~21 & 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

- SridharKritha

Answer 8

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

- user5914697

---

虽然仅包含代码的答案在简单情境下是有效的，如果它们是正确的，请记住它们是不推荐的。请尽量提供至少解释代码中最关键部分的代码在做什么以及如何或为什么这样做。在这种特定情况下，建议还提供到BigInteger(String)和Scanner.nextInt()的官方文档链接。 - CosmicGiant

Answer 9

我需要看一些例子才能确定，但你可能因为二进制补码算术而得到意外的值。如果该数字具有前导零（例如在26的情况下），则~运算符会将其翻转为前导1，从而导致负数。

一个可能的解决方法是使用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的回答也可能有所帮助

- Ben Sutton

---

@Ben 除了 Java 没有无符号类型（在这里不是真正的问题，但有点烦人）之外，如果它允许位操作，解决方案与 C 或任何其他语言中的解决方案相同 - 这是一个便宜的借口 ;) 但是，确保执行此类函数需要更多的时间不会有影响，并且该解决方案易于理解和简单。本身并不差 - 只是缺少良好数学解决方案的某种优雅性，我个人认为。 - Voo

@Peter 我认为我的“不会太久”不应该被字面理解。另外，考虑到现代CPU的频率仍然只有约<5*10^9Hz，皮秒有点“乐观” ;) - Voo

@Voo，大多数现代CPU的时钟速度都在2-3.3 GHz左右，一些高端CPU甚至可以达到5.1 GHz。按位取反通常是一个单周期指令。 - Peter Lawrey

@Peter，但遗憾的是1Ghz意味着一个周期的执行需要1ns而不是1ps。你需要一颗1Thz的CPU才能在1ps内完成一个时钟周期。我不明白为什么我们要争论10%的速度差异，当我所知道的最快的CPU（某些超频到9ghz左右的p4）仍然比太慢了一个数量级。 - Voo

@Voo，一颗1.1 GHz的处理器（智能手机速度）仍然有900 ns的时钟周期，而3.3 GHz的处理器大约是300 ps。没有太多的个人电脑是1 GHz。 - Peter Lawrey

Answer 10

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

- prashant

---

这是一个合理的建议，但已经有类似的内容发布了。 - harold