mathassemblybinarybit-manipulationarithmetic-expressions

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

From Hacker's Delight: 2nd Edition:

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.

Solution

• 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)`