在特定索引处移除位

Question

我基本上想在特定的索引处从整数中删除一位。也就是说，我不想取消/清除该位；我实际上想要剥离它，以便每个更高位都向下移动，替换其位置上的相应位。从视觉上来看，这可以与从数组中删除元素或从字符串中删除字符进行比较。

为了更清楚地说明，以下是一些示例：

1011011 (original number)
    ^ index = 2
0101111 (result)

10000000000000000000000000000001
^ index = 31
00000000000000000000000000000001

1111111111111111111111111111110
                              ^ index = 0
0111111111111111111111111111111

我充满信心地开始移动一些位，然后想出了下面的Java方法...

public static int removeBit(int num, int i) {
    int out = (num >>> (i + 1)) << i;
    out  |= (num << (32 - i)) >>> (32 - i);
    return out;
}

...这几乎总是有效的，除了一些极端情况：

10000000000000000000000000000001 (= Integer.MAX_VALUE - 1)
^ index = 31, results in:
10000000000000000000000000000001

1011011
      ^ index = 0, results in:
1111111

换句话说，如果索引为0或31（最低位或最高位），我的方法将输出垃圾值。

我似乎无法理解它，这就是为什么我要问：如何从32位整数中删除任意位？

我特别寻找在Java中执行此操作的最有效方式（内存和CPU消耗最小），因为此操作必须运行至少数百万次。这就是为什么像“将其转换为字符串，删除字符并转换回来”之类的方法不可行的原因。

- MCL

---

我怀疑这是针对上限的：num >>> (i + 1)。向左移动32位与不移动相同（右操作数事先得到AND掩码处理）。 - Marko Topolnik

@MarkoTopolnik 我也怀疑是这样的。你有什么想法可以改变我的方法，以便不会发生这种情况吗？当然，我可以加入一些 if 语句，但我认为在性能方面可能有更简单的选择。 - MCL

如果if语句很便宜，我不会太早开始担心它。仅仅使用位操作方法就可以保证出色的性能（几个纳秒）。首先让它工作，然后进行分析，如果必要再进行优化（这种情况非常少见）。 - Marko Topolnik

你说“这样每个高位都向上移动”。看起来高位应该向下移动或低位向上移动。 - Hot Licks

@HotLicks 您说得完全正确。那更多是翻译问题（长话短说）... - MCL

(32 - i)——这是低端错误的源头。再次超出了31。 - Marko Topolnik

Answer 1

正如评论中所解释的那样，转移计数滚动到>=32时会出现问题。

无论如何，让我们推导一种做法。

首先考虑这两个“部分”，低位部分（它在原始位置上被复制，并且可以是0..31位长）和高位部分（其向下移位一个并且也可以是0..31位长）。这两个部分的总长度始终为31。

低位部分的掩码很明显：~(-1 << i)

这使得高位部分的掩码变得明显：~lowmask << 1。高位部分已经进行了移位，因此该移位可以进行。

现在剩下的就是将这两个部分取或运算，你将会得到

static int removeBit(int x, int i)
{
    int mask = ~(-1 << i);
    return (x & mask) | ((x >>> 1) & ~mask);
}

消除双重否定：

static int removeBit(int x, int i)
{
    int mask = -1 << i;
    return (x & ~mask) | ((x >>> 1) & mask);
}

- harold

---

很好的解释，我自己永远想不到。我觉得我的大脑不适合位运算 ;) - MCL

出于好奇：如果我们将索引31定义为LSB，将索引0定义为MSB，这对性能有影响吗？或者说：我能否利用统计趋势，使位更可能位于整数的右半部分还是左半部分？ - MCL

@MCL 镜像索引可以通过使用“-1 <<（31-i）”（等效地，“-1 <<（i ^ 31）”）作为掩码来完成，这将需要额外的操作，并且差异应该是可测量的（尽管很小）。我认为没有任何可能利用任何统计倾向 - 它无论如何都需要恒定的时间，至少在具有桶移位器的任何处理器上。 - harold

Answer 2

只需要屏蔽所需的位，无需来回移位。

public static int removeBit(int num, int index) {
    int mask = (1 << index) - 1;
    return ((num & ((~mask) << 1)) >>> 1) | (num & mask);
}

或者

public static int removeBit(int num, int index) {
    int mask = (1 << index) - 1;
    return ((num >>> 1) & ~mask) | (num & mask);
}

一些平台具有非常高效的并行位提取，因此如果您可以在JNI中完成工作，或者如果Java具有类似于Bmi2.ParallelBitExtract的内置功能，则可以这样做。

public static int removeBit(int num, int index) {
    return Bmi2.ParallelBitExtract(num, ~(1 << index));
}

- phuclv

---

这段代码揭示了我符号位运算分析器中的一个错误，但它仍然是错误的。对于 index = 0 是正确的，但对于任何其他索引，它只对 num 的可能值的一半正确。例如，考虑 index = 1 和 num = odd。mask = 1，因此 OR 右侧始终为零，并且 num 的第 0 位从未出现在结果中。 - harold

@harold 在看到这个问题后才想到的，还没有测试过。我刚刚编辑了代码。 - phuclv

Answer 3

如果使用最少的指令很重要，对于这种位操作，通常最好计算需要切换的位，然后使用异或运算符来应用。此外，与哈罗德的解决方案相比，这样可以节省一条指令。

static int removeBit(int x, int i)
{
    int mask = -1 << i;
    return ((x ^ (x >>> 1)) & mask) ^ x;
}

或者

static int removeBit(int x, int i)
{
    return (((x ^ (x >>> 1)) >>> i) << i) ^ x;
}

- Falk Hüffner