java - 删除特定索引处的位

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 消耗)，因为此操作必须至少运行几百万次。这就是为什么像“将其转换为字符串，删除字符并将其转换回来”这样的事情是不可能的。

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