Let \(r = k2^m\) where \(k\) is odd.
Case 1: \(k \text { mod } 4 = 1\). Then \(k\) is of the form \(k=4n+1\). In binary, \(k = \cdots b_2b_101\) and therefore \[r = \cdots b_2b_1 01\underbrace{00\cdots0}_{m}\] Now \(-r\) is expressed using the method of two's complement. To do this, you take the complement of all the binary bits in \(r-1\). Since \[r-1 = \cdots b_2b_1 00\underbrace{11\cdots1}_{m}\] then \[-r = \overline{\cdots}\; \overline{b_2}\;\overline{b_1}11\underbrace{00\cdots0}_{m}\] where \(\overline{b}\) represent the complement of the binary digit \(b\). The bitwise AND operator, &, compares the binary digits of two integers and returns 1 wherever both numbers have a 1 and 0 elsewhere. Therefore \[r \,\& \,-\!r = \cdots 0001\underbrace{00\cdots0}_{m} \] The bitwise left shift operator, << < 1, shifts the binary bits to the left 1 position, replacing the vacant rightmost position with 0. So \[(r \,\& \,-\!r) \lt \lt 1 = \cdots 0010\underbrace{00\cdots0}_{m} \] Comparing this with the binary representation of \(r\) gives the result \[ ((r \,\& \,-\!r) \lt \lt 1) \; \& \; r = \cdots 0000\underbrace{00\cdots0}_{m} = 0\]
Case 2: \(k \text { mod } 4 = 3\). Then \(k\) is of the form \(k = 4n+3\). In binary, \(k = \cdots b_2b_111\) and therefore \[r = \cdots b_2b_1 11\underbrace{00\cdots0}_{m}\] Following the steps above gives the following results:
\(r =\) | \(\cdots b_2b_1 11\underbrace{00\cdots0}_{m}\) |
\(-r =\) | \(\overline{\cdots}\; \overline{b_2}\;\overline{b_1}01\underbrace{00\cdots0}_{m}\) |
\(r \,\& \,-\!r =\) | \(\cdots 0001\underbrace{00\cdots0}_{m} \) |
\((r \,\& \,-\!r) \lt \lt 1 =\) | \(\cdots 0010\underbrace{00\cdots0}_{m} \) |
\( ((r \,\& \,-\!r) \lt \lt 1) \; \& \; r =\) | \(\cdots 0010\underbrace{00\cdots0}_{m} \ne 0\) |
Individual corner
r =