Removing bit at specific index

Question

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

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

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: 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.

Answer 1

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

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

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.

The mask for the low piece is obvious: ~(-1 << i)

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

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

Throw out the double negation:

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

Answer 2

Just mask out the bits needed, no need to shift back and forth

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

or

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

Some platforms have very efficient parallel bit extract so if you can do the job in JNI or if Java has some intrinsic similar to Bmi2.ParallelBitExtract then you can do like this

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

Answer 3

If it is important to use the minimum number of instructions, for these kind of bit shuffling it is often best to calculate the bits that need to be toggled and then use xor to apply that. Also here this saves one instruction compared to harold's solution:

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

or

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