4.6.4 Example of Incrementing Binary Integers

• Consider an algorithm to continually increment a binary integer by 1. Start at the LSB (least significant bit, i.e. right most bit); while the current bit is 1, change it to 0 and move left, stopping when we reach far left or hit a 0 bit, which we change to 1 and stop.
• For the credit balance, take the total number of 1s in the binary integer:

Step i Integer t_iC_ia_i

0 --- 0000 ---- - 0 -

1 --- 0001 ---- 1 1 2

2 --- 0010 ---- 2 1 2

3 --- 0011 ---- 1 2 2

4 --- 0100 ---- 3 1. 2

5 --- 0101 ---- 1 2 2

6 --- 0110 ---- 2 2 2

7 --- 0111 ---- 1 3 2

8 --- 1000 ---- 4 1 2

9 --- 1001 ---- 1 2 2

10 --- 1010 ---- 2 2 2

11 --- 1011 ---- 1 3 2

12 --- 1100 ---- 3 2 2

13 --- 1101 ---- 1 3 2

14 --- 1110 ---- 2 3 2

15 --- 1111 ---- 1 4 2

16 --- 0000 ---- 4 0 0