Sorry, another K&R question! "Exercise 2-9: In a two's complement number system x &= (x - 1) deletes the rightmost 1-bit in x. Explain why."

I worked this out and (I guess incorrectly) determined that more than the rightmost 1-bit will be deleted. I know that in two's complement, the negative number is formed by taking the complement and adding 1. Then to perform subtract the negative number is added, and the high-carry bit is discarded.

So let's take x = 8, and I'll use 2 bytes for brevity:

x = 00001000

So to do x - 1 we actually add -1? So the complement of 1 is: 11111110 and adding 1 we get 11111111

Then we have: 00001000 11111111 = 00000111

which is the answer we expect. Next we're going to & that result with x, and assign it back to x: 00001000 &00000111 = 00000000

in which it appears I've made some sort of mistake because more than the right-most bit got deleted.

CodePudding user response：

You worked it out perfectly. I think you just misunderstand what is meant by "the right-most 1-bit" (you keep just saying "rightmost bit", omitting the "1-bit" from the original prompt).

00001000 only has a single 1 bit. After the operation, that 1 bit is gone; as you showed, you're left with 00000000. It's doing exactly what it says on the tin, finding the 1 that is closest to the right hand side and deleting it (all the 0 bits to the right of that 1 bit remain unchanged, as do all the bits to the left of it, whether they are 0 or 1). If you work out the same math with 00110000, you'll find the result to be 00100000, removing the rightmost 1-bit, flipping it to a 0. 0111 becomes 0110, 0110 becomes 0100, etc.