Worries

You might worry that even though a power of two fits into an integer, perhaps it should not be part of the representation.

For example, the above table shows that 52 will be represented as 1 _ _ _ _ _.

Perhaps, instead, it should be represented as 0 _ _ _ _ _ (where the low-order bits are yet to be determined).

This is not a problem, for two reasons:

1. The representation of an integer in this method of unsigned binary is unique.
   • If an integer is represented as bN bN-1 . . . b1 b0 (each b either 1 or 0 ) then that is the only way it can be represented.
   • So once you find the powers of 2 that add up to the integer, you have found the only correct representation.
2. No pattern of bits to the right of the bit in position N represents more than 2^N.
   • So if 2^N fits into an integer, and is the largest power of 2 that fits, then no other pattern of bits results in a better fit.
   • For example, 16 = 10000, and 15 = 01111.
   • So be sure to start with the leftmost bit, the largest power of two that fits.

So your job (using this method) is:

1. Find the high-order bit of the binary representation of an integer.
2. Subtract that power of 2 from the integer.
3. Then find the rest of the bits by doing this again and again.