2
$\begingroup$

Prove that for a n-bit word $x$ the operation

$$x \& (x - 1)$$

with $\&$ being the bitwise AND-operator, turns off (inverts) the rightmost bit of $x$ (e.g. 0101100 -> 01010000). The example above is is the first bit manipulation presented in Henry Warren's Hacker's Delight and I would like to understand why this works.

A concrete mathematical proof or even pointers to a general strategy when undertaking proofs regarding bitstrings would be higly appreciated.

$\endgroup$
0
$\begingroup$

Consider the binary representation of $x-1$. Reading from left to right, it is the same as the representation of $x$ until we get to the last one bit of $x$. That bit and all subsequent zero bits are flipped in $x-1$. So all when you take the bitwise exclusive or, all bits prior to the last one bit in $x$ are the same, and all bits starting from the last one bit are zero.

For example $1100100 - 1 = 1100011$. It's just like a terminal string of $0$'s turning into $9$'s when you subtract $1$ in decimal.

$\endgroup$
  • $\begingroup$ Thanks for the quick answer :-) $\endgroup$ – user532913 Feb 19 '18 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy