Hacker's Delight

2-1. Manipulating Rightmost Bits

Some of the formulas in this section find application in later chapters.

Use the following formula to turn off the rightmost 1-bit in a word, producing 0 if none (e.g., 01011000 ⇒ 01010000):

This may be used to determine if an unsigned integer is a power of 2; apply the formula followed by a 0-test on the result.

Similarly, the following formula can be used to test if an unsigned integer is of the form 2ⁿ − 1 (including 0 or all 1’s):

Use the following formula to isolate the rightmost 1-bit, producing 0 if none ...