How does the formula x & (x - 1) works?

user_14515133 0
Viewed 2247

From Hacker's Delight: 2nd Edition:

Formula to turn off the rightmost 1-bit of a word.

The formula here seems a little bit awkward here. How is some x vector is subtracted from 1 vector (presumbly 0x1111 1111) when x is smaller than 1? (Like: (as given in example) 0x0101 1000 - 0x0000 0000 doesn't make any sense to me) The former is a smaller number than the first one and the words aren't storing signed vectors either. Is that something related to RISC specific here or what?

As specified in the notation section of the book. A bold letter corresponds a vector for word like x = 00000000. And a bold one differs from a light face 1. As bold 1 = 11111111 which is an 8 bit word.

Edit2: Special Thanks to Paul Hankin to figure out the unconventional notations used here. A bold faced one refers to 32 bit size word which is [00000001] and a light faced 1 refers to a number one as in C.

arithmetic-expressions bit-manipulation math assembly binary
2 Answers

Subtracting 1

Since we're more familiar with decimal than with binary, it sometimes helps to look at what happens in decimal.

What happens when subtracting 1 in decimal? Take for example 1786000 - 1 = 1785999.

If you subtract 1 from a positive number x in decimal:

  • all the zeroes at the right of x become 9;
  • the rightmost nonzero digit of x becomes 1 less;
  • other digits are unaffected.

Now, in binary, it works exactly the same, except we only have 0 1 instead of 0 123456789.

If you subtract 1 from a number x in binary:

  • all the zeroes at the right of x become 1;
  • the rightmost nonzero bit of x becomes 0;
  • other bits are unaffected.

What about negative numbers? Happily, representation using 2's complement is such that negative numbers behave exactly like positive numbers. In fact, when looking at the bits of x, you can subtract 1 from x without needing to know whether x is a signed int or an unsigned int.

x & (x-1)

Let's start with an example: x = 01011000. We can subtract 1 the way I just explained:

x   = 01011000
x-1 = 01010111

Now what's the result of the bitwise-and operation x & (x-1)? We take the two bits in each column; if they are both 1, we write 1; if at least one of them is 0, we write 0.

x       = 01011000
x-1     = 01010111
x&(x-1) = 01010000

What happened?

  • all the zeroes at the right of x remain zero;
  • the rightmost 1 of x becomes a 0 because of x-1;
  • all other bits are unaffected, because they are the same in x and x-1.

Conclusion: we have zeroed the rightmost 1 of x, and left all other bits unaffected.

user_30807230

Let's take a look at an what x-1 does. Assume x is a value '???? 1000 (? are 0 or 1)
=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000

It's very similar no matter where the right most 1 is placed within x.

Requested example:
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110

P.s. x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)

user_19212730
Related