删除特定索引处的位 [英] Removing bit at specific index

问题描述

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

为了清楚起见，一些例子：

I'm basically trying to remove a bit from an integer at a specific index. That is, I do not want to unset/clear the bit; I actually want to strip it, so that every higher bit moves down, replacing the respective bit at its position. Visually, this could be compared to deleting an element from an array or removing a character from a string.
For the sake of clarity, some examples:

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

10000000000000000000000000000001
^ index = 31
00000000000000000000000000000001

1111111111111111111111111111110
                              ^ index = 0
0111111111111111111111111111111

充满信心，我开始转移一些位，并提出了以下Java方法......

Full of confidence, I started shifting some bits, and came up with the following Java method...

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

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

...which almost always works, except for some extreme cases:

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

1011011
      ^ index = 0, results in:
1111111

换句话说，如果索引是0或31（最小或最重要的位），我的方法将输出垃圾。

我似乎无法绕过它，这就是为什么我问：

In other words, if the index is 0 or 31 (least or most significant bit), my method will output garbage.
I can't seem to wrap my head around it, and that's why I'm asking:

如何删除32位整数中的任意位？

我特别想找到性能最好的在Java中这样做的方法（尽可能小的内存和CPU消耗），因为这个操作必须运行至少几百万次。这就是为什么像将它转换为字符串，删除字符并将其转换回来之类的东西是不可能的。

How can I remove an arbitrary bit in a 32-bit integer?
I'm especially looking for the most performant way to do it in Java (smallest possible memory and CPU consumption), since this operation has to run at least a couple million times. That's why something like "convert it into a string, remove the char and convert it back" is out of the question.

推荐答案

正如评论中所解释的那样，班次计数翻到> = 32，这造成了麻烦。

As explained in the comments, the shift counts rolled over to >= 32, which caused trouble.

无论如何，让我们找到一种方法。

Anyway, let's derive a way to do it.

首先考虑两个碎片，低碎片（在原始位置复制，可能在0 ... 31位长之间）和高片（转移）向下一个，也可以在0 ... 31位长之间）。碎片的总长度始终为31。

Start by considering the two "pieces", the low piece (which gets copied in its original position and may be anywhere between 0 .. 31 bits long) and the high piece (which gets shifted down by one, and can also be between 0 .. 31 bits long). The total length of the pieces is always 31.

低块的掩码很明显：〜（-1<< i）

这使得高件的面具显而易见： ~lowmask<< 1 。无论如何，高件都会移动，所以换班就可以了。

Which makes the mask for the high piece obvious: ~lowmask << 1. The high piece is shifted anyway, so that shift can go.

现在剩下的就是把它们和OR一起拿走，你就得到了

Now all that's left is to take the pieces and OR them together, and you would get

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

这篇关于删除特定索引处的位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！