13

I'm preparing for an interview using the text, "Cracking the Coding Interview" by Gayle Laakman McDowell. On the section covering bit manipulation, there are two functions that are provided, but I don't quite understand how it works.

// To clear all bits from the most significant bit through i (inclusive), we do:
int clearMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

// To clear all bits from i through 0 (inclusive), we do:
int clearBitsIthrough0(int num, int i) {
    int mask = ~(((1 << (i+1)) - 1);
    return num & mask;
}

In the first function, I understand what (1 << i) does of course, but what I'm not sure of is how subtracting 1 from this value affects the bits (i.e., (1 << i) - 1)).

I basically have the same confusion with the second function. To what effects, specifically on the bits, does subtracting 1 from ((1 << (i+1)) have? From my understanding, ((1 << (i+1)) results in a single "on" bit, shifted to the left i+1 times--what does subtracting this by 1 do?

Thanks and I hope this was clear! Please let me know if there are any other questions.

For those who by some chance have the text I'm referencing, it's on page 91 in the 5th Edition.

  • Read [this](http://stackoverflow.com/questions/15729765/why-does-the-output-of-applied-on-a-negative-number-is-filled-with-ones-on-th) and [this](http://stackoverflow.com/questions/15708493/what-is-the-meaning-of-this-declaration) answers – Grijesh Chauhan Apr 04 '13 at 17:03

4 Answers4

29

let's assume i= 5

(1 << i) give you 0100000 the 1 is placed in the 6th bit position

so now if we substract 1 from it, then we get 0011111 ==> only the 5 first bit are set to 1 and others are set to 0 and that's how we get our mask

Conclusion: for a giving i the (1 << i) -1 will give you a mask with the i first bits set to 1 and others set to 0

MOHAMED
  • 41,599
  • 58
  • 163
  • 268
  • Good answer and well explained – David Ranieri Apr 04 '13 at 16:52
  • @MOHAMED could you explain further why the subtraction does that? In a generic way I mean... what is happening behind the curtains? Is there a way to demonstrate the result for any `i`? – tomasyany Jul 29 '16 at 16:32
  • 3
    @tomasyany it follows from the way you count in binary: 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... so on. Notice when you take a step backward from any 100...00 number you get a 11..11 with one less digit. – Trevor Merrifield Aug 26 '16 at 16:05
6

For the first question:

lets say i = 5

(1 << i )    = 0010 0000 = 32 in base 10
(1 << i ) -1 = 0001 1111 = 31

So a & with this mask clears the most significant bit down to i because all bit positions above and including index i will be 0 and any bellow will be 1.

For the second question:

Again lets say i = 5

  (1 << (i + 1))      = 0100 0000 = 64 in base 10
  (1 << (i + 1)) - 1  = 0011 1111 = 63
~((1 << (i + 1)) - 1) = 1100 0000 = 192

So a & with this masks clears bits up to index i

Robert Prior
  • 508
  • 4
  • 14
4

First Function:

Let's take i=3 for example. (1 << i) would yield 1000 in binary. Subtracting 1 from that gives you 0111 in binary (which is i number of 1's). ANDing that with the number will clear all but the last i bits, just like the function description says.

Second Function:

For the second function, the same applies. If i=3, then ((i << (i+1)) - 1) gives us 01111. The tilde inverts the bits, so we have 10000. It's important to do it this way instead of just shifting i bits left, because there could be any number of significant bits before our mask (so 10000 could be 8 bits long, and look like 11110000. That's what the tilde gets us, just to be clear). Then, the number is ANDed with the mask for the final result

Stephen Fischer
  • 2,445
  • 2
  • 23
  • 38
3

// To clear all bits from the most significant bit through i (inclusive), we do:

int clearMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

Take the example of i = 3
1<<3 gives you 0x00001000 
(1<<3)-1 gives you 0x00000111
num & (1<<i)-1 will clear the bits from msb to i

// To clear all bits from i through 0 (inclusive), we do:

int clearBitsIthrough0(int num, int i) {
    int mask = ~(((1 << (i+1)) - 1);
    return num & mask;
}

same example of i = 3 gives you

1 <<(3+1) =0x00010000
1 <<(3+1)-1 = 0x00001111
mask =~(1<<(3+1)-1) = 0x11110000
num & mask will cleaR the bits from 0 throuh i
user2243395
  • 51
  • 3