Understanding the arithmetic in `(1 << j) - 1`

Question

Would appreciate help in explaining the following bit operation. Pardon my lack of understanding of bit arithmetic.

int max = ~0;   
int left = max - ((1 << j) - 1); 

What will be the result of this operation? Is (1<<(j-1)) equivalent to ((1 << j) - 1)?

Answer 1

Follow the below formulas,

• Case : 1

  (1 << j) - 1) is equal to 2^j-1 [j = 1,2...]
  

• Case : 2

  (1<<(j-1)) is equal to 2^(j-1) [j = 1,2,3...]
  

Is (1<<(j-1)) equivalent to ((1 << j) - 1)?

No, Obviously from above formulas.

What will be the result of this operation?

For this question, max will be "-1" [bitwise NOT(0) is equivalent to complement of all bit values of 0]

then formula will be

left = -(2^j)

If j = -1 or j = 0, then the above formulas won't work as expected, because 1<<-1 is undefined behavior in C. More details found at below links.

https://stackoverflow.com/a/4945765/3979414

http://c0x.coding-guidelines.com/6.5.7.html

Answer 2

(1 << j) - 1 is a number with j one bits on the right

        j bits
       ┌──────┐
00...0011...111

max is a number with all one bits

11...1111...111

Each one bit from max will become 0 when subtracting from the one bit from (1 << j) - 1, and remain 1 otherwise. Hence max - ((1 << j) - 1) will produce a value with j zero bits on the right

           j...210 ← bit position
    11...1111...11
 -  00...0011...11
──────────────────
    11...1100...00

That means the result is the bitwise not of (1 << j) - 1, i.e.

max - ((1 << j) - 1) == ~((1 << j) - 1)

Is (1<<(j-1)) equivalent to ((1 << j) - 1)?

1 << (j-1) shifts 1 j-1 places to the left and produces 2^{j - 1}, so it has j-1 zeros on the right followed by a one 100...00. (1 << j) - 1 gives a number with j zeros on the right which is 2^j - 1, as said above. Can you guess they're similar or not?