CODEWITHSUNDEEP
javabit-manipulationbit
Harish Kayarohanam
Harish Kayarohanam

Reputation: 4024

To clear bits from i through 0 - bit manipulation

I was going to Cracking the Coding Interview chapter 5 Bit manipulation and found way to clear bits from i through 0 in number num

int mask = ~(-1 >>> (31 - i));
return num & mask

Though the above works

Can we make it simple like

int mask = (-1 << (i+1));
return num & mask;

Am I missing any corner cases ?

Upvotes: 1

Views: 241

Answers (2)

user555045
user555045

Reputation: 64903

There is indeed an edge case: for i = 31, (-1 << (i+1)) = -1 while ~(-1 >>> (31 - i)) = 0.

This happens because shift counts are taken modulo the size (in bits) of the type, in this case 32, (31 + 1) mod 32 = 0 so in both expressions the effective shift count is zero. They then act differently because of the inverted logic of the second expression.

However, ~(-1 >>> (31 - i)) is equivalent to the simpler -2 << i.

Upvotes: 1

Jacob G.
Jacob G.

Reputation: 29710

Absolutely. Your mask -1 << (i+1) is logically equivalent to the book's mask ~(-1 >>> (31 - i)).

Your method bit-wise shifts -1 to the left i + 1 times, filling the lowest i + 1 bits with 0.

The book's method logically shifts -1 to the right 31 - i times, filling the highest 31 - i bits with 0. However, it then inverts the bits, which is what makes yours equivalent to it. To verify it for all values of int, you can create a simple for-loop:

for (int i = 0; i < 31; i++) {
    System.out.println(~(-1 >>> (31 - i)) + " " + (-1 << (i+1)));
}

When running it, you'll see that both masks are equivalent at every iteration.

Upvotes: 1

Related Questions