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

Question

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

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

00000000000000000010011110000100  // Input
00000000000000000001100001111011  // Expected

我如何在java/C++中实现这一点？？

Answer 1

我们可以执行以下操作。对于给定的n = 10011110000100

1. 我们将找到2v = 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);

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

二次方的重复行，其目的是在m中设置n的最高有效集位和所有低于它的有效位，如果你有权访问这样的东西，可以用一条特殊的指令来代替，以找到前导零的数量。

Answer 3

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

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。