Source code online books for professionals by professionals

WhY BINarY WOrKS
We’ve just seen that when summing up the powers of two, you always get one less than the next power of two. 
For example, 1 + 2 + 4 = 8 – 1, or 1 + 2 + 4 + 8 = 16 – 1, and so forth. This is, from one perspective, exactly 
why binary counting works. a binary number is a string of zeros and ones, each of which determines whether 
a given power of two should be included in a sum (starting with 2
0
 = 1 on the far right). So, for example, 11010 
would be 2 + 8 + 16 = 26. Summing the first h of these powers would be equivalent to a number like 1111, with 
h ones. This is as far as we get with these h digits, but luckily, if these sum to n–1, the next power will be exactly 
n. For example, 1111 is 15, and 10000 is 16. (exercise 3-3 asks you to show that this property lets you represent 
any positive integer as a binary number.)
Here’s the first lesson about doubling, then: A perfectly balanced binary tree (that is, a rooted tree where all 
internal nodes have two children and all leaves have the same depth) has n–1 internal nodes. There are, however, a 
couple more lessons in store for you on this subject. For example, I still haven’t touched upon the hare and tortoise 
hinted at in the section heading.
The hare and the tortoise are meant to represent the width and height of the tree, respectively. There are several 
problems with this image, so don’t take it too seriously, but the idea is that compared to each other (actually, as a 
function of each other), one grows very slowly, while the other grows extremely fast. I have already stated that n = 2
h
, 
but we might just as easily use the inverse, which follows from the definition of the binary logarithm: h = lg n;  
see Figure 
3-3
 for an illustration.
n = 2
h
h = 
lg
n