切换除最高设置位之后的所有位

Toggle all bits except after highest set bit

除了最高设置位之后，我如何切换数字的所有位？

例如： 假设需要切换一个 32 位数字。

00000000000000000010011110000100  // Input

00000000000000000001100001111011  // Expected

我怎样才能在 java/C++ 中实现这一目标？？

我们可以做到以下几点。对于给定的 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);

你可以这样做：

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的幂重复的行，其目的是在m中设置n的最高有效位和所有比它低的位，可以用特殊指令代替查找前导零的数量（如果您有权访问此类内容）。

以下实现说明了 David Eisenstat 使用的 2 的幂的有效使用，但在提供任意大整数的语言中，例如 Python 或 Ruby。换句话说，这些解决方案不是硬连线的 32 位整数。我测试了 Ruby 版本，输入大到 21000.

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，我也相信您的话。