反转最高位之后的所有位

Question

如何翻转一个数的所有位（除了最高位及之后的位）？

例如：假设有一个需要翻转的32位数字。

00000000000000000010011110000100  // Input

00000000000000000001100001111011  // Expected

我怎样才能在Java/C++中实现这个？

- sn-

---

显示为“// Expected”的值并不是我期望的，解释为“翻转一个数字的所有位，除了最高位之后的位”，并查看“// Input”：最高位设置也被翻转了。如果尝试改进措辞，请在标题中使用多个位。 - greybeard

Answer 1

我们可以按照以下步骤操作，以给定的 n = 10011110000100 为例：

1. 找到 最小的 2 的幂 v = 100...00，使得 v > n。
2. 然后计算 result = n ^ (v - 1)（注意，b XOR 1 可以 切换 第 b 位的值）。

具体解释如下：

n           =  10011110000100
v           = 100000000000000
v - 1       =  11111111111111
n ^ (v - 1) =  01100001111011

代码：

int n = 0b10011110000100;

int v = 1;

while (v <= n)
  v <<= 1;

int result = n ^ (v - 1);

- Dmitry Bychenko

Answer 2

你可以像这样做：

public static int toggle(int n) {
  int m = n;
  m |= m >>> 1;
  m |= m >>> 2;
  m |= m >>> 4;
  m |= m >>> 8;
  m |= m >>> 16;
  return n ^ m;
}

重复的以2的幂次方为主的行，其目的是将n的最高位比特和所有比它低的比特设置为m，可以通过使用特殊指令来查找前导零的数量来替换。

如果您可以访问这种功能，那么可以用这种方式替换代码。

- David Eisenstat

Answer 3

以下实现展示了David Eisenstat使用2的幂次方的高效方法，但是在提供任意大整数的语言中（例如Python或Ruby）使用。换句话说，这些解决方案并没有针对32位整数进行硬编码。我使用尽可能大的输入测试了Ruby版本，最大测试值为2的1000次方。

Ruby

def toggle(n)
  shift = 1
  m = n
  while (1 << shift) <= n
    m |= m >> shift
    shift <<= 1
  end
  m ^ n
end

Python

def toggle(n):
  shift = 1
  m = n
  while (1 << shift) <= n:
    m |= m >> shift
    shift <<= 1
  return m ^ n

您使用了标签language-agnostic，因此我会按照您的意思进行翻译，即使您在问题中提到了C++和Java。

- pjs